Advertisement
sylviapsh

Quick Sort An Array Of Strings

Jan 11th, 2013
44
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.85 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. class QuickSortArrayOfStrings
  6. {
  7.   static void Main()
  8.   {
  9.     //Write a program that sorts an array of strings using the quick sort algorithm (find it in Wikipedia).
  10.  
  11.     //Initialize the string list for sort
  12.     List <string> stringList = new List<string>{"home", "space", "room", "sofa", "lamp", "furniture", "bed", "book", "bookshelf" };
  13.     //Call the Partition method
  14.     stringList = Partition(stringList);
  15.  
  16.     //Print the result on the console
  17.     foreach (string item in stringList)
  18.     {
  19.       Console.WriteLine("{0} ", item);
  20.     }
  21.   }
  22.  
  23.   static List<string> Partition(List<string> partitionList)
  24.   {
  25.     List<string> beforePivot = new List<string>(); //A list for the elements before the pivot
  26.     List<string> afterPivot = new List<string>();//A list for the elements after the pivot
  27.  
  28.     if (partitionList.Count > 0)
  29.     {
  30.       int pivotIndex = partitionList.Count / 2; //Different possibilities here. I take the middle element
  31.       string pivotString = partitionList[pivotIndex]; //Keep the pivot element so that we could generate the new partition list
  32.  
  33.       for (int i = 0; i < partitionList.Count; i++)
  34.       {
  35.         if (i != pivotIndex)
  36.         {
  37.           if (string.Compare(partitionList[i], pivotString) <= 0) //compare the current string to the pivot one and add it to the correct partition
  38.           {
  39.             beforePivot.Add(partitionList[i]);
  40.           }
  41.           else
  42.           {
  43.             afterPivot.Add(partitionList[i]);
  44.           }
  45.         }
  46.       }
  47.  
  48.       beforePivot = Partition(beforePivot);
  49.       afterPivot = Partition(afterPivot);
  50.  
  51.       partitionList.Clear();
  52.       partitionList.AddRange(beforePivot);
  53.       partitionList.Add(pivotString);
  54.       partitionList.AddRange(afterPivot);
  55.     }
  56.  
  57.     return partitionList;
  58.   }
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement