Skip to main content

QuickSort


This is similar to Median Sort, which I skipped, but Quicksort supersedes it.  This uses a similar strategy, but instead of finding the median, it accepts any value for the pivot index, then simply performs an insertion sort on the resulting partitioned array of 2 sub-arrays.  The insertion sort used here is from a prior post on Insertion Sort.

 Class

 using System;

 namespace Algorithms
{
    class QuickSort
    {
        public void Sort()
        {
            //creates array
            int[] arrayToSort = { 11, 1, 22, 2, 33, 3, 44, 4, 55, 5, 66, 6, 7, 77 };
            //gets pivotIndex, set at midpoint of arry
            int pivotIndex = Partition(arrayToSort, 0, arrayToSort.Length - 1, (arrayToSort.Length - 1)/2);
            //sorts each ~half array
            arrayToSort = InsertionSort.Sort(arrayToSort, 0, pivotIndex);
            arrayToSort = InsertionSort.Sort(arrayToSort, pivotIndex, arrayToSort.Length - 1);
       }

         public int Partition(int[] arrayToSort, int startIndex, int endIndex, int pivotIndex)
        {
            //swap pivot index with end index
            int lastValue = arrayToSort[endIndex];
            int pivotValue = arrayToSort[pivotIndex];
            arrayToSort[pivotIndex] = lastValue;
            arrayToSort[endIndex] = pivotValue;
            
            ////then start with arr[0]
            ////move right
            ////find first value less than value put at arr[end]
            ////move that value into arr[0] and move arr[0] into arr[?] of value found
            ////find next value less than arr[end]
            int moveTo = startIndex;
            for (int counter = startIndex; counter <= endIndex; counter++)
            {
                int temp = arrayToSort[counter];
                if (temp < arrayToSort[endIndex])
                {
                    arrayToSort[counter] = arrayToSort[moveTo];
                    arrayToSort[moveTo] = temp;
                    moveTo += 1;
                }
            }
            int tmp = arrayToSort[endIndex];
            arrayToSort[endIndex] = arrayToSort[moveTo];
            arrayToSort[moveTo] = tmp;
            
            //returns pivot index (index of partition value)
            return moveTo;
        }
    }
}

Labels:

Comments

Post a Comment

Popular posts from this blog

Heap Sort

Heap Sort is interesting because the use of the 'heapify' method that creates a binary tree as a flat array. First, a binary tree, also known as a heap , is created, and then the same function is used to sort the elements. In a heap, the first node in the array at zero (0) is the top node of the binary tree. The next two (2) items are the two (2) subnodes of the top node, and so on.  For each node at a position (positionIndex), its 2 subnodes are in the following positions: int left = 2 * positionIndex + 1; int right = 2 *  positionIndex + 2; The CommonMethods.Swap() function is a reusable class , since swapping values by position is a common action during these example sorts. Class using System; namespace Algorithms {     class HeapSort     {         public int[]  Sort()         {             //creates array             int[] arrayToSort = { 11, 1, 22, 2, 33, 3, 44, 4, 55, 5, 66, 6, 7, 77, 88 };                         //creates a heap             BuildH
6 comments
Read more

Hash-based Search

An example of a hash-based search, although using dictionaries.  The code is designed to manage lists of Person objects, with unique Id's as the key value, with a rudimentary hash function to assign to various lists. Salient Characteristic(s) Useful for managing large unsorted lists Divides the items into smaller hash-based buckets (divide and conquer) Generally excellent performance Sensitive to the choice of hash function and data structures chosen Note The Id key is not rigorous enough to guarantee uniqueness, and a better key might need to be selected, e.g., SSN, to prevent the same person being entered twice. Code using System; using System.Collections.Generic; namespace Algorithms {     //Example object to add and find in Hash Search example     public class Person     {         private int _Id;         public int Id          {             get { return _Id; }             set { _Id = value; }          }                  private string _LastName;
Post a Comment
Read more

Review - TFS/VSTS - Great Product, Ideal for Small Development Shops

This is a report a short review I provided for G2 regarding TFS : What do you like best? If you use Visual Studio for development, TFS, or its online equivalent VSTS, you can have a fairly seamless end-to-end integration. Out of the box, it provides code management, testing, work hierarchy in agile formats, automated build, and deployment. What do you dislike? Branching and merging can be a bit painful, in that it needs to be planned, and is not natively part of the process. Code review also needs to be planned and only recently has it become part of the process. Recommendations to others considering the product My only concern regarding TFS and VSTS is that Microsoft itself recommends using Git. What business problems are you solving with the product? What benefits have you realized? In my current role, I've joined a shop that has application development as secondary to their role of desktop OS and app deployment/maintenance, so their code management practi
Post a Comment
Read more