CODEWITHSUNDEEP
arraysalgorithmsortingquicksort
Kat Pantle
Kat Pantle

Reputation: 41

Basic Quick Sort: listing array with each partition call

Given array 8, 5, 3, 7, 1, 6, 4, 2. List array to show the array changes in memory. You may list out array after each partition call is terminated.

Im not sure I understand the question, but if Im simply running through the quick sort algorithm, the pivot or mid value seems to be 2. Does that mean the 1st partition is at index 2? (8,5,3) & (7,1,6,4,2)? What is the next step? Im not getting this sort algorithm :( Newb stuff I know, but I am being thrown into this pretty quickly.

Thanks in advance!

Upvotes: 0

Views: 507

Answers (1)

Kushagra Misra
Kushagra Misra

Reputation: 481

you have to show how your array is getting sorted in each step. It is preferred to show your selected pivot in console and then show the changes happens in array. for recursive operation print array before making next call, I am sharing the code below

public class Quicksort
{
  int[] array;

  public int[] sort(int[] array)
  {
    int[] result= null;
    this.array = array;

    sort(0, array.length-1);
    return this.array;
 }

 public void sort(int lowerIndex, int heigherIndex)
 {
    int i= lowerIndex;
    int j= heigherIndex;
    int piviot = array[(lowerIndex + ((heigherIndex-lowerIndex)/2))];
    System.out.println("Piviot selected " + piviot);
    while (i<=j)
    {
        while (array[i]<piviot)
            i++;

        while (array[j]>piviot)
            j--;

        if(i<=j)
        {
            exchange(i,j);
            i++;
            j--;
        }
    }
    printArray();
    if (lowerIndex<j)
        sort(lowerIndex,j);
    if (heigherIndex>i)
        sort(i,heigherIndex);
 }

 private void printArray(){
    for(int x:array)
    {
        System.out.print(x + " ");
    }
    System.out.println();
 }

 private void exchange(int i, int j)
 {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
 }

 public static void main(String[] args) {
    Quicksort quicksort = new Quicksort();
    int[] input = {24,2,45,20,56,75,2,56,99,53,12};
    quicksort.sort(input);

 }
 }

Upvotes: 1

Related Questions