使用就地排序算法对对象进行排序

本文概述

• C ++
• Java
• Python3
• C#

给定一个数组红, 蓝色和黄色对象, 则任务是使用就地排序算法对数组进行排序, 以使所有蓝色对象出现在所有红色对象之前, 所有红色对象出现在所有黄色对象之前。

例子：

输入： arr[] = {“blue”, “red”, “yellow”, “blue”, “yellow”}
输出：blue blue red yellow yellow
输入：arr[] = {“red”, “blue”, “red”, “yellow”, “blue”}
输出：blue blue red red yellow

方法:首先，使用哈希表将蓝色、红色和黄色对象的值分别映射为1、2和3。现在，当需要比较两个对象时，请使用这些映射值。因此，该算法将对对象数组进行排序，使所有蓝色对象(映射到值1)首先出现，然后是所有红色对象(映射到值2)，然后是所有黄色对象(映射到值3)。

下面是上述方法的实现：

C ++

//C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
//Partition function which will partition
//the array and into two parts
int partition(vector<string>& objects, int l, int r, unordered_map<string, int>& hash)
{
     int j = l - 1;
  
     int last_element = hash[objects[r]];
  
     for ( int i = l; i <r; i++) {
  
         //Compare hash values of objects
         if (hash[objects[i]] <= last_element) {
             j++;
             swap(objects[i], objects[j]);
         }
     }
  
     j++;
  
     swap(objects[j], objects[r]);
  
     return j;
}
  
//Classic quicksort algorithm
void quicksort(vector<string>& objects, int l, int r, unordered_map<string, int>& hash)
{
     if (l <r) {
         int mid = partition(objects, l, r, hash);
         quicksort(objects, l, mid - 1, hash);
         quicksort(objects, mid + 1, r, hash);
     }
}
  
//Function to sort and print the objects
void sortObj(vector<string>& objects)
{
  
     //Create a hash table
     unordered_map<string, int> hash;
  
     //As the sorting order is blue objects, //red objects and then yellow objects
     hash[ "blue" ] = 1;
     hash[ "red" ] = 2;
     hash[ "yellow" ] = 3;
  
     //Quick sort function
     quicksort(objects, 0, int (objects.size() - 1), hash);
  
     //Printing the sorted array
     for ( int i = 0; i <objects.size(); i++)
         cout <<objects[i] <<" " ;
}
  
//Driver code
int main()
{
  
     //Let's represent objects as strings
     vector<string> objects{ "red" , "blue" , "red" , "yellow" , "blue" };
  
     sortObj(objects);
  
     return 0;
}

Java

//Java implementation of the approach
import java.util.*;
class GFG 
{
  
//Partition function which will partition
//the array and into two parts
static int partition(Vector<String> objects, int l, int r, Map<String, Integer> hash)
{
     int j = l - 1 ;
  
     int last_element = hash.get(objects.get(r));
  
     for ( int i = l; i <r; i++) 
     {
  
         //Compare hash values of objects
         if (hash.get(objects.get(i)) <= last_element) 
         {
             j++;
             Collections.swap(objects, i, j);
         }
     }
  
     j++;
  
     Collections.swap(objects, j, r);
  
     return j;
}
  
//Classic quicksort algorithm
static void quicksort(Vector<String> objects, int l, int r, Map<String, Integer> hash)
{
     if (l <r)
     {
         int mid = partition(objects, l, r, hash);
         quicksort(objects, l, mid - 1 , hash);
         quicksort(objects, mid + 1 , r, hash);
     }
}
  
//Function to sort and print the objects
static void sortObj(Vector<String> objects)
{
  
     //Create a hash table
     Map<String, Integer> hash = new HashMap<>();
  
     //As the sorting order is blue objects, //red objects and then yellow objects
     hash. put( "blue" , 1 );
     hash. put( "red" , 2 );
     hash. put( "yellow" , 3 );
  
     //Quick sort function
     quicksort(objects, 0 , objects.size() - 1 , hash);
  
     //Printing the sorted array
     for ( int i = 0 ; i <objects.size(); i++)
         System.out.print(objects.get(i) + " " );
}
  
//Driver code
public static void main(String []args)
{
     //Let's represent objects as strings
     Vector<String> objects = new Vector<>(Arrays.asList( "red" , "blue" , "red" , "yellow" , "blue" ));
  
     sortObj(objects);
}
}
  
//This code is contributed by PrinciRaj1992

Python3

# Python3 implementation of the approach
  
# Partition function which will partition
# the array and into two parts
objects = []
hash = dict ()
  
def partition(l, r):
     global objects, hash
     j = l - 1
  
     last_element = hash [objects[r]]
  
     for i in range (l, r):
  
         # Compare hash values of objects
         if ( hash [objects[i]] <= last_element):
             j + = 1
             (objects[i], objects[j]) = (objects[j], objects[i])
  
     j + = 1
  
     (objects[j], objects[r]) = (objects[r], objects[j])
  
     return j
  
# Classic quicksort algorithm
def quicksort(l, r):
     if (l <r):
         mid = partition(l, r)
         quicksort(l, mid - 1 )
         quicksort(mid + 1 , r)
  
# Function to sort and print the objects
def sortObj():
     global objects, hash
  
     # As the sorting order is blue objects, # red objects and then yellow objects
     hash [ "blue" ] = 1
     hash [ "red" ] = 2
     hash [ "yellow" ] = 3
  
     # Quick sort function
     quicksort( 0 , int ( len (objects) - 1 ))
  
     # Printing the sorted array
     for i in objects:
         print (i, end = " " )
  
# Driver code
  
# Let's represent objects as strings
objects = [ "red" , "blue" , "red" , "yellow" , "blue" ]
  
sortObj()
  
# This code is contributed 
# by Mohit Kumar

C#

//C# implementation of the approach
using System;
using System.Collections.Generic;
  
class GFG 
{
  
//Partition function which will partition
//the array and into two parts
static int partition(List<String> objects, int l, int r, Dictionary<String, int> hash)
{
     int j = l - 1;
     String temp;
     int last_element = hash[objects[r]];
  
     for ( int i = l; i <r; i++) 
     {
  
         //Compare hash values of objects
         if (hash[objects[i]] <= last_element) 
         {
             j++;
             temp = objects[i];
             objects[i] = objects[j];
             objects[j] = temp;
         }
     }
  
     j++;
  
     temp = objects[r];
     objects[r] = objects[j];
     objects[j] = temp;
  
     return j;
}
  
//Classic quicksort algorithm
static void quicksort(List<String> objects, int l, int r, Dictionary<String, int> hash)
{
     if (l <r)
     {
         int mid = partition(objects, l, r, hash);
         quicksort(objects, l, mid - 1, hash);
         quicksort(objects, mid + 1, r, hash);
     }
}
  
//Function to sort and print the objects
static void sortObj(List<String> objects)
{
  
     //Create a hash table
     Dictionary<String, int> hash = new Dictionary<String, int>();
  
     //As the sorting order is blue objects, //red objects and then yellow objects
     hash.Add( "blue" , 1);
     hash.Add( "red" , 2);
     hash.Add( "yellow" , 3);
  
     //Quick sort function
     quicksort(objects, 0, objects.Count - 1, hash);
  
     //Printing the sorted array
     for ( int i = 0; i <objects.Count; i++)
         Console.Write(objects[i] + " " );
}
  
//Driver code
public static void Main(String []args)
{
     //Let's represent objects as strings
     List<String> objects = new List<String>{ "red" , "blue" , "red" , "yellow" , "blue" };
  
     sortObj(objects);
}
}
  
//This code is contributed by Rajput-Ji

输出如下：

blue blue red red yellow

---