Given an array of n integers, we have to reverse sort the array elements such the equal keys are stable after sorting.
Examples:
Input : arr[] = {4, 2, 3, 2, 4}
Output : 4, 4, 3, 2, 2
Prerequisite : Stability in sorting algorithms
Method 1 (Writing our own sorting function : Bubble Sort)
We know sorting algorithms like Bubble Sort, Insertion Sort, Merge Sort, Count Sort are stable. We implement here Bubble Sort.
Explanation
First Pass
(4′, 2′, 3, 2″, 4″) -> (2′, 4′, 3, 4″, 2″) Here algorithm compares last two element and
swaps since 2″ < 4″.
(2′, 4′, 3, 4″, 2″) -> (2′, 4′, 4″, 3, 2″) swap since 3 < 4″
(2′, 4′, 4″, 3, 2″) -> (2′, 4′, 4″, 3, 2″)
(2′, 4′, 4″, 3, 2″) -> (4′, 2′, 4″, 3, 2″) swap since 2′ < 4′.
Second Pass:
(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″) swap since 2′ (4′, 4″, 2′, 3, 2″)
Third Pass:
(4′, 4″, 2′, 3, 2″) -> (4′, 4″, 2′, 3, 2″)
(4′, 4″, 2′, 3, 2″) -> (4′, 4″, 3, 2′, 2″) swap since 2′<3
Now, the array is in sorted order and same elements are in same order as they were in the original array.
C++
#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;
}
|
Java
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);
}
}
|
Python3
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#
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);
}
}
|
PHP
<?php
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 );
?>
|
Javascript
<script>
function print(a,n)
{
for (let i = 0; i <= n; i++)
document.write(a[i] + " " );
document.write( "<br>" );
}
function sort(a,n)
{
for (let i = n;
i >= 0; i--)
for (let j = n;
j > n - i; j--)
if (a[j] > a[j-1]){
let tempswap = a[j];
a[j] = a[j - 1];
a[j - 1] = tempswap;
}
print(a, n);
}
let n = 6;
let a=[];
a.push(2);
a.push(4);
a.push(3);
a.push(2);
a.push(4);
a.push(5);
a.push(3);
sort(a, n);
</script>
|
Time Complexity: O(n*n)
Auxiliary Space: O(1)
Method 2 (Using library function)
We can use stable_sort to sort elements in stable manner.
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] + " " );
}
}
}
|
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 = " " )
|
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] + " " );
}
}
}
|
Javascript
<script>
function reverse(a)
{
var i, k, n = a.length;
var t;
for (i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
}
var arr = [ 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 ] ;
var n = arr.length;
arr.sort();
reverse(arr);
document.write( "Array after sorting : " + "<br>" );
for ( var i = 0; i < n; ++i)
{
document.write(arr[i] + " " );
}
</script>
|
Array after sorting :
9 8 7 6 5 4 3 2 1 0
Time Complexity: O(n logn)
Auxiliary Space: O(1)