Thread: Quicksort

  1. #1
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020

    Quicksort

    Hi,

    I tried to write the source code myself but there're tons of errors. And even if i can compile i bet it doesn't work. I need a solution. I need to study. Pls help. Thnx. Note that i need to use recursive techniques.

    THis is what i have just to prove that i really tried myself:

    Code:
    /* Quicksort */
    
    #include <stdio.h>
    
    #define SIZE 10
    
    void quicksort( int array[], int starting, int ending );
    void partition( int array, int arraySize, int starting, int ending );
    
    int main()
    {
       int array[ SIZE ] = { 37, 2, 6, 4, 89, 8, 10, 12, 68, 45 };
       int i;
    
       quicksort( array, 0, 9 );
    
       for ( i = 0; i < SIZE; i++ )
          printf( "%d ", array[ i ] );
    
       printf( "\n" );
    
       getch();
       return 0;
    }
    
    void partition( int array, int arraySize, int starting, int ending )
    {
       int temp;
       int i, end = 0;
       int rightmost = ending;
       int ele = starting;
       int swapsMade = 0;
       int leftmost;
    
       while ( end != 1 ) {
    
          for ( i = rightmost; i >= 0; i-- ) {
             if ( array[ i ] < array[ ele ] ) {
                temp = array[ ele ];
                array[ ele ] = array[ i ];
                array[ i ] = temp;
                temp = ele;
                ele = i;
                leftmost = temp;
                swapsMade++;
                break;
             }
          }
    
          for ( i = leftmost; i < arraySize; i++ ) {
             if ( array[ i ] > array[ ele ] ) {
                temp = array[ ele ];
                array[ ele ] = array[ i ];
                array[ i ] = temp;
                temp = ele;
                ele = i;
                rightmost = temp;
                swapsMade++;
                break;
             }
         }
    
         if ( swapsMade == 0 )
            end = 1;
       }
    }
    
    void quicksort( int array[], int starting, int ending )
    {
       int i;
       int inOrder = 0;
    
       for ( i = 0; i < SIZE - 2; i++ )
          if ( array[ i ] < array[ i + 1 ] )
             inOrder = 1;
    
       if ( inOrder != 1 )
          partition( array, SIZE, starting, ending );
    }

  2. #2
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    I worked on this quickly because I have my own work to do, but this is the idea.

    Code:
    #include<stdlib.h>
    #include<stdio.h>
    #include<string.h>
    
    
    int IsLess(int x, int mid)
    {
    	if(x < mid)
    		return -1;
    	else
    		return 1;
    }
    
    int GetRecord(int a[], int x)
    {
    	return a[x];
    }
    
    void QSort(int a[], int left, int right)
    {
    	int i = left;
    	int j = right;
    
    	//get middle record
    	int temp = GetRecord(a, (i+j) / 2);
    
    	do
    	{
    		while (IsLess(GetRecord(a,i), temp) < 0 && i < right)
    			i++;
    
    		while (IsLess(temp,GetRecord(a,j)) < 0 && j > left)
    			j--;
    
    		//swap
    		if( i <= j)
    		{
    			int temp;
    			temp = a[i];
    			a[i] = a[j];
    			a[j] = temp;
    			i++;
    			j--;
    		}
    	}while( i <= j);
    
    	//recursive calls
    	if(left < j)
    		QSort(a,left,j);
    	if(i < right)
    		QSort(a,i,right);
    }
    
    int main()
    {
    	const int size = 10;
    	int array[size] = { 37, 2, 6, 4, 89, 8, 10, 12, 68, 45 };
    
    	QSort(array, 0, size - 1);
    	
    	for(int i = 0; i < size; i++)
    		printf("%d ",array[i]);
    	return 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help needed to perform quicksort on list
    By lazyme in forum C++ Programming
    Replies: 8
    Last Post: 05-15-2009, 02:38 AM
  2. Scalability problems with Quicksort
    By hbejkosa in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2008, 11:26 PM
  3. Problems with Quicksort and Pointers
    By algatt in forum C Programming
    Replies: 3
    Last Post: 10-10-2007, 04:24 AM
  4. Using quicksort and radix sort for an anagram program
    By RazielX in forum C Programming
    Replies: 2
    Last Post: 05-03-2004, 09:33 AM
  5. quicksort problem
    By spinner in forum C Programming
    Replies: 9
    Last Post: 05-04-2003, 02:02 PM