Quickly sorting using Quick Sort Algorithm

Quick sort algorithm and the tutorial is explained nicely  .

I have used the following steps for using quick sort:

  1. Select the first element as pivot.
  2. Position it properly in the array by comparing it from end of array.
  3. Reassign the pivot with the newly swapped element.
  4. Compare it with the starting of the array.
  5. Reassign the pivot with the next element from left side.
  6. Repeat steps 2-5 until the array is sorted.

public void sort(int arr[])
{
int pi = 0,
temp=0;

int leftpi = -1 ,
rightpi=arr.length-1,
count = 0;

boolean leftsorted = false,rightsorted = false;

System.out.println(“=================================”);
for(int a:arr)
{

System.out.print(a+” | “);
}

do{

pi = leftpi + 1;
System.out.println(“\n==========PASS “+(++count)+”==================”);
for(int i = arr.length -1 ; (i >=0 && i > leftpi) ; i– )
{

if(arr[pi] > arr[i])
{
temp = arr[i];
arr[i] = arr[pi];
arr[pi] = temp;

System.out.println(“Pivot=”+arr[pi]);

for(int a:arr)
{

System.out.print(a+” | “);
}

leftpi = pi;
pi = i ;
leftsorted = true;
break;
}
}

for(int j = 0; (j<arr.length || j<rightpi-1) ; j++)
{
if(arr[pi] < arr[j])
{
temp = arr[j];
arr[j] = arr[pi];
arr[pi] = temp;

System.out.println(“Pivot=”+arr[pi]);

for(int a:arr)
{

System.out.print(a+” | “);
}

rightpi = pi ;
pi = j ;
rightsorted = true;
break;
}
}

if(!leftsorted && !rightsorted)
{
System.exit(0);
}

leftsorted = false;
rightsorted = false;

}while(leftpi<=rightpi);
}

 

While this gives me the sorted array but I think there are some passes in the above iteration which can be skipped. Still trying for a better solution. Keep safe and happy coding 🙂

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s