Quick Sort is a popular sorting algorithm because it usually achieves optimal O(

ID: 3696519 • Letter: Q

Question

Quick Sort is a popular sorting algorithm because it usually achieves optimal O(n log n) running time in practice. However, in the worst case, the running time can be quadratic. The method to choose the pivot is crucial to avoid the worst cases. The purpose of this homework is to evaluate experimentally the performance of Quick Sort for different methods of choosing the pivot, and compare with Selection Sort, which is simpler but quadratic. Write a method that implements Selection Sort. Write methods for two versions of Quick Sort, depending on how the pivot is chosen from each subaray to be sorted, as follows. Choose the pivot from the first position of the subarray. Choose three positions of the siibarrav at random and make the median of the values in these positions the pivot. Write attest program that measures the running time of the above three methods while sorting 1000000 numbers (adjust the quantity if needed). Use three types of inputs: already sorted in increasing order, already sorted in decreasing order, and an input with the numbers generated at random. Fill in the following chart with the running times observed. Draw conclusions from the values observed. Are the measureme significantly different for some cases ? why? How the pivot choice helps for those cases where the running time is smaller?

Explanation / Answer

a) write a Method To Implement selection sort in java.

The selection sort is a combination of searching and sorting. During each pass, the unsorted element with the smallest (or largest) value is moved to its proper position in the array. The number of times the sort passes through the array is one less than the number of items in the array. In the selection sort, the inner loop finds the next smallest (or largest) value and the outer loop places that value into its proper location.

An Example To Demonstrate The Selection Sort :

Selection sort is not difficult to analyze compared to other sorting algorithms since none of the loops depend on the data in the array. Selecting the lowest element requires scanning all n elements (this takes n 1 comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n 1 elements and so on, for (n 1) + (n 2) + ... + 2 + 1 = n(n 1) / 2 (n2) comparisons. Each of these scans requires one swap for n 1 elements.

package com.java2novice.algos;

public class MySelectionSort {

public static int[] doSelectionSort(int[] arr){

for (int i = 0; i < arr.length - 1; i++)

{

int index = i;

for (int j = i + 1; j < arr.length; j++)

if (arr[j] < arr[index])

index = j;

int smallerNumber = arr[index];

arr[index] = arr[i];

arr[i] = smallerNumber;

}

return arr;

}

public static void main(String a[])

int[] arr1 = {10,34,2,56,7,67,88,42};

int[] arr2 = doSelectionSort(arr1);

for(int i:arr2){

System.out.print(i);

System.out.print(", ");

}

Output:

2, 7, 10, 34, 42, 56, 67, 88,

Performance Of The Selection Sort Algorithm :

Worst Case : O(n^2)

Average Case : O(n^2)

Best Case : O(n^2)

b) a) choose the pivot from the first position of the subarray
b) Choose Three Positions Of the Subarray at random and make the median of the values in these positionsthe pivot

counter = 0
def partition(myList, left, right): #left and right are the start and end indixes of the subarray
#Make the counter global so that it will increment up and the quicksort function can return it
global counter

if (len(myList)%2!=0): # if odd length array
x = left + (right-left)/2
list1 = []
list1.append(myList[left])
list1.append(myList[x])
list1.append(myList[right])

list1.sort()
middle = list1[1]

else: # if even length array
#x = (len(myList)-1)//2
x = left + (right-left)/2
list1 = []
list1.append(myList[left])
list1.append(myList[x])
list1.append(myList[right])

list1.sort()
middle = list1[1] # Gives values-- match the value of the pivot of 3 pivot rule to the index position in list

if (middle==myList[left]):
pivot = myList[left] # choose first element in subarray as pivot
else if (middle==myList[right]):
myList[left],myList[right] = myList[right],myList[left] # need to swap first with last position

pivot = myList[left] # choose first element in subarray as pivot
else if (middle==myList[x]):
#Make swap between first and median element to make the pivot the median element
myList[left],myList[x] = myList[x],myList[left] # need to swap median with first position
pivot = myList[left] # choose first element in subarray as pivot

# i is the boundary for what we have looked at already and separates what is less than, greater than pivot
i = left+1
# j is the boundary for what we have looked at and what we have not looked at
j = left+1

for j in range(left+1, right + 1):
counter += 1
if myList[j] < pivot: # if myList[j] > pivot, then do nothing
myList[j],myList[i]= myList[i], myList[j] # do the swap
i += 1

myList[left],myList[i-1]=myList[i-1],myList[left] # swap where pivot needs to be
position = i-1 # Keep track of location of pivot by index
return position #new pivot position. Used to divide the next left and right side of the array.

def quicksort(myList, left, right):
if left < right:# this is enough to end recursion
pivot_pos = partition(myList, left, right)

len(myList[left:pivot_pos - 1])
len(myList[pivot_pos + 1:right])

quicksort(myList, left, pivot_pos - 1)
quicksort(myList, pivot_pos + 1, right)
return myList,counter

.......................................................

for size 10 array, first = 25, last = 29, median = 21
>>> blist = [3,9,8,4,6,10,2,5,7,1]
>>> quicksort(blist,0,9)
([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 25)

for size 100 array, first = 615 last = 587, median = 518
>>> clist = [57, 97, 17, 31, 54, 98, 87, 27, 89, 81, 18, 70, 3, 34, 63, 100, 46, 30, 99,
10, 33, 65, 96, 38, 48, 80, 95, 6, 16, 19, 56, 61, 1, 47, 12, 73, 49, 41, 37,
40, 59, 67, 93, 26, 75, 44, 58, 66, 8, 55, 94, 74, 83, 7, 15, 86, 42, 50, 5, 22,
90, 13, 69, 53, 43, 24, 92, 51, 23, 39, 78, 85, 4, 25, 52, 36, 60, 68, 9, 64, 79,
14, 45, 2, 77, 84, 11, 71, 35, 72, 28, 76, 82, 88, 32, 21, 20, 91, 62, 29]
>>> quicksort(clist,0,99)

([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48,
49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71,
72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94,
95, 96, 97, 98, 99, 100], 615)

first = 31, last = 35, median = 24
>>> dlist = [2,5,4,3,0,9,8,6,1,20,17]
>>> quicksort(dlist,0,10)
([0, 1, 2, 3, 4, 5, 6, 8, 9, 17, 20], 31)

zlist = [0,9,8,7,6,5,4,3,2,1]
quicksort(zlist,0,9)
answer is 25 for median

array1
quicksort(array1,0,9999)
median = 138382

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{

class SortComparison
{
          static void Main(string[] args)
        {
                 int[] arr_selection = new int[10];   // change the value here if you want to run the code for 100   or 1000 elements
                int[] arr_insertion = new int[10];
                int[] arr_bubble = new int[10];
                int[] arr_merge = new int[10];
                int[] arr_quick = new int[10];
                Random rn = new Random();
                for (int i = 0; i < arr_selection.Length; i++)
                {
                       arr_selection[i] = rn.Next(1, 10000);

}

                  Random rn4 = new Random();
                 System.Diagnostics.Stopwatch sw4 = new System.Diagnostics.Stopwatch();
                for (int i = 0; i < arr_quick.Length; i++)
                {
                            arr_quick[i] = rn3.Next(1, 10000);
                  }
                 sw4.Start();
                quicksort(arr_quick, 0, arr_quick.Length - 1);
                sw4.Stop();
                long timequick= sw4.ElapsedTicks / (System.Diagnostics.Stopwatch.Frequency / (1000L * 1000L));
               Console.WriteLine("time taken by quick sort is:{0} microseconds", timequick);

static void quicksort(int[] x,int first,int last){
int pivot,j,temp,i;

                if(first<last){
                pivot=first;
                i=first;
                j=last;

               while(i<j){
               while(x[i]<=x[pivot]&&i<last)
                i++;

                while(x[j]>x[pivot])
                 j--;
                 if(i<j){
                 temp=x[i];
                 x[i]=x[j];
                 x[j]=temp;
      }
}

         temp=x[pivot];
         x[pivot]=x[j];
          x[j]=temp;
         quicksort(x,first,j-1);
         quicksort(x,j+1,last);

}
}