Рубрики

Стабильная сортировка по убыванию

Учитывая массив из n целых чисел, мы должны выполнить обратную сортировку элементов массива, чтобы равные ключи были устойчивыми после сортировки.
Примеры:

Input : arr[] = {4, 2, 3, 2, 4}
Output : 4, 4, 3, 2, 2

Условие: стабильность в алгоритмах сортировки

Метод 1 (Написание нашей собственной функции сортировки: Bubble Sort )

Мы знаем, что алгоритмы сортировки, такие как Bubble Sort , Insertion Sort , Merge Sort , Count Sort стабильны. Мы реализуем здесь Bubble Sort.

объяснение
Первый проход
(4 ′, 2 ′, 3, 2 ″, 4 ″) -> (2 ′, 4 ′, 3, 4 ″, 2 ″). Здесь алгоритм сравнивает последние два элемента и
свопы с 2 ″ <4 .
(2 ′, 4 ′, 3, 4 ″, 2 ″) -> (2 ′, 4 ′, 4 ″, 3, 2 ″) своп с 3 <4
(2 ′, 4 ′, 4 ″, 3, 2 ″) -> (2 ′, 4 ′, 4 ″, 3, 2 ″)
(2 ′, 4 ′, 4 ″, 3, 2 ″) -> (4 ′, 2 ′, 4 ″, 3, 2 ″) своп, так как 2 ′ <4 ′.

Второй проход:
(4 ′, 2 ′, 4 ″, 3, 2 ″) -> (4 ′, 2 ′, 4 ″, 3, 2 ″)
(4 ′, 2 ′, 4 ″, 3, 2 ″) -> (4 ′, 2 ′, 4 ″, 3, 2 ″)
(4 ′, 2 ′, 4 ″, 3, 2 ″) -> (4 ′, 4 ″, 2 ′, 3, 2 ″) своп с 2 ′ (4 ′, 4 ″, 2 ′, 3, 2 ″ )

Третий проход:
(4 ′, 4 ″, 2 ′, 3, 2 ″) -> (4 ′, 4 ″, 2 ′, 3, 2 ″)
(4 ′, 4 ″, 2 ′, 3, 2 ″) -> (4 ′, 4 ″, 3, 2 ′, 2 ″) своп, так как 2 ′ <3
Теперь массив находится в отсортированном порядке, и те же элементы находятся в том же порядке, что и в исходном массиве.

C ++

// Bubble sort для реализации сортировки
// элементы в порядке убывания.
#include <iostream>
#include <vector>

using namespace std;

  

void print(vector<int> a, int n)

{

    for (int i = 0; i <= n; i++) 

        cout << a[i] << " ";    

    cout << endl;

}

  
// сортирует [] в порядке убывания, используя
// пузырьковая сортировка.

void sort(vector<int> a, int n)

{

    for (int i = n; i >= 0; i--) 

        for (int j = n; j > n - i; j--) 

            if (a[j] > a[j - 1]) 

                swap(a[j], a[j-1]);

    print(a, n);

}

  
// Код драйвера

int main()

{

    int n = 7;

    vector<int> a;

    a.push_back(2);

    a.push_back(4);

    a.push_back(3);

    a.push_back(2);

    a.push_back(4);

    a.push_back(5);

    a.push_back(3);

    sort(a, n - 1);

    return 0;

}

Джава

// Bubble sort реализация
// сортировать элементы в
// в порядке убывания.

import java.io.*;

import java.util.*;

  

class GFG

static void print(ArrayList<Integer> a, 

                                 int n)

{

    for (int i = 0; i <= n; i++) 

        System.out.print(a.get(i) + " "); 

    System.out.println();

}

  
// сортирует [] по убыванию
// заказ с использованием пузырьковой сортировки.

static void sort(ArrayList<Integer> a,

                                  int n)

{

    for (int i = n; 

            i >= 0; i--) 

        for (int j = n; 

                j > n - i; j--) 

            if (a.get(j) > a.get(j - 1)) 

            {

                int tempswap = a.get(j);

                a.remove(j);

                a.add(j, a.get(j - 1)); 

                a.remove(j - 1);

                a.add(j - 1, tempswap); 

            }

    print(a, n);

}

  
// Код драйвера

public static void main(String[] args)

{

    int n = 6;

    ArrayList<Integer> a = new ArrayList<Integer>();

    a.add(2);

    a.add(4);

    a.add(3);

    a.add(2);

    a.add(4);

    a.add(5);

    a.add(3);

    sort(a, n);

}
}

  
// Этот код предоставлен
// Маниш Шоу (manishshaw1)

python3

# Bubble sort для реализации сортировки
# элементы в порядке убывания.

  

def print1(a, n):

  

    for i in range(0,n+1):

        print(a[i],end=" "

    print("")

  

  
# Сортирует [] в порядке убывания, используя
# пузырьковая сортировка.

def sort(a, n):

  

    for i in range(n,0,-1): 

        for j in range(n, n - i,-1): 

            if (a[j] > a[j - 1]): 

                a[j], a[j-1]=a[j-1], a[j]

    print1(a,n)

  

  
# Код драйвера

n = 7

a = [2,4,3,2,4,5,3]

  

sort(a, n-1)

  
# Этот код добавлен
# Смита Динеш Семвал

C #

// Bubble sort реализация
// сортировать элементы в
// в порядке убывания.

using System;

using System.Collections.Generic;

  

class GFG

static void print(List<int> a, 

                       int n)

{

    for (int i = 0; i <= n; i++) 

        Console.Write(a[i] + " "); 

    Console.WriteLine();

}

  
// сортирует [] по убыванию
// заказ с использованием пузырьковой сортировки.

static void sort(List<int> a,

                      int n)

{

    for (int i = n; 

             i >= 0; i--) 

        for (int j = n; 

                 j > n - i; j--) 

            if (a[j] > a[j - 1]) 

            {

                int tempswap = a[j];

                a[j] = a[j - 1]; 

                a[j - 1] = tempswap; 

            }

    print(a, n);

}

  
// Код драйвера

static void Main()

{

    int n = 6;

    List<int> a = new List<int>();

    a.Add(2);

    a.Add(4);

    a.Add(3);

    a.Add(2);

    a.Add(4);

    a.Add(5);

    a.Add(3);

    sort(a, n);

}
}

  
// Этот код предоставлен
// Маниш Шоу (manishshaw1)

PHP

<?php
// Bubble sort реализация
// сортировать элементы в
// в порядке убывания.

  

function swap(&$x, &$y)

{

    $x ^= $y ^= $x ^= $y;

}

  

function print1($a, $n)

{

    for ($i = 0; $i <= $n; $i++) 

        echo ($a[$i] . " ");

    echo ("\n");

}

  
// сортирует [] по убыванию
// заказ с использованием пузырьковой сортировки.

function sort1($a, $n)

{

    for ($i = $n;

         $i >= 0; $i--)

    {

        for ($j = $n

             $j > $n - $i; $j--) 

        {

            if ($a[$j] > $a[$j - 1]) 

                swap($a[$j], 

                     $a[$j - 1]);

        }

    }

    print1($a, $n);

}

  
// Код драйвера

$n = 6;

$a = array();

array_push($a, 2);

array_push($a, 4);

array_push($a, 3);

array_push($a, 2);

array_push($a, 4);

array_push($a, 5);

array_push($a, 3);

sort1($a, $n);

  
// Этот код предоставлен
// Маниш Шоу (manishshaw1)
?>


Выход:

5 4 4 3 3 2 2

Метод 2 (Использование библиотечной функции)
Мы можем использовать stable_sort для стабильной сортировки элементов.

C ++

// C ++ программа для демонстрации по убыванию
// стабильная сортировка с использованием БОЛЕЕ <> ().
#include <bits/stdc++.h>

using namespace std;

  

int main()

{

    int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };

    int n = sizeof(arr) / sizeof(arr[0]);

  

    stable_sort(arr, arr + n, greater<int>());

  

    cout << "Array after sorting : \n";

    for (int i = 0; i < n; ++i)

        cout << arr[i] << " ";

  

    return 0;

}

Джава

// Java-программа для демонстрации в порядке убывания
// стабильная сортировка с использованием БОЛЕЕ <> ().

import java.util.*;

  

class GFG 

{

    static void reverse(int a[]) 

    

        int i, k, n = a.length; 

        int t;

        for (i = 0; i < n / 2; i++)

        

            t = a[i]; 

            a[i] = a[n - i - 1]; 

            a[n - i - 1] = t; 

        

    }

      

    // Код драйвера

    public static void main(String[] args)

    {

        int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};

        int n = arr.length;

  

        Arrays.sort(arr);

        reverse(arr);

  

        System.out.println("Array after sorting : \n");

        for (int i = 0; i < n; ++i)

        {

            System.out.print(arr[i] + " ");

        }

    }

  
// Этот код предоставлен 29AjayKumar

Python 3

# Программа Python 3 для демонстрации
# в порядке убывания

  

if __name__ == "__main__":

      

    arr = [ 1, 5, 8, 9, 6,

            7, 3, 4, 2, 0 ]

    n = len(arr)

  

    arr.sort(reverse = True)

  

    print("Array after sorting : ")

    for i in range(n):

        print(arr[i], end = " ")

  
# Этот код предоставлен ita_c

C #

// C # программа для демонстрации по убыванию

using System;

      

class GFG 

{

    static void reverse(int []a) 

    

        int i, k, n = a.Length; 

        int t;

        for (i = 0; i < n / 2; i++)

        

            t = a[i]; 

            a[i] = a[n - i - 1]; 

            a[n - i - 1] = t; 

        

    }

      

    // Код драйвера

    public static void Main(String[] args)

    {

        int []arr = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};

        int n = arr.Length;

  

        Array.Sort(arr);

        reverse(arr);

  

        Console.WriteLine("Array after sorting : \n");

        for (int i = 0; i < n; ++i)

        {

            Console.Write(arr[i] + " ");

        }

    }

  
// Этот код предоставлен 29AjayKumar


Выход:

Array after sorting : 
9 8 7 6 5 4 3 2 1 0 

Рекомендуемые посты:

Стабильная сортировка по убыванию

0.00 (0%) 0 votes