Thread: Merge Sort (Array)

  1. #1
    Registered User
    Join Date
    Mar 2011
    Posts
    2

    Exclamation Merge Sort (Array)

    Cannot see what is wrong with my code: Currently trying to sort an array using merge sort.

    Code:
    #include <iostream>
    
    #define SIZE 4
    
    void mergeSort(float arraySorted[], float arrayTemp[], int LHS, int RHS);
    void mergeBack(float arraySorted[], float arrayTemp[], int LHS, int middle, int RHS);
    
    void main(){
    	
    	int Counter=0;
    	float arrayOne[SIZE] = {65, -72, 54, 238};
    	float arrayTwo[SIZE];
    
    
    
    		for (Counter=SIZE-1;Counter>=0;Counter--){
    			std::cout << arrayOne[Counter] << std::endl;
    		}
    
    	std::cout << "Something about sorting:" << std::endl;
    	mergeSort(arrayOne, arrayTwo, 0, SIZE-1);
    
    		for (Counter=SIZE-1;Counter>=0;Counter--){
    			std::cout << arrayOne[Counter] << std::endl;
    		}
    
    
    	std::cout << "Blah" << std::endl;
    }
    
    void mergeSort(float arraySorted[], float arrayTemp[], int LHS, int RHS){
    
    	int Counter, middle;
    
    		if (RHS > LHS){
    			middle = (LHS + RHS) / 2;
    
    			mergeSort(arraySorted, arrayTemp, LHS, middle);
    			mergeSort(arraySorted, arrayTemp, (middle+1), RHS);
    
    			mergeBack(arraySorted, arrayTemp, LHS, middle, RHS);
    		}
    
    }
    
    void mergeBack(float arraySorted[], float arrayTemp[], int LHS, int middle, int RHS){
    
    	int LHSEnd, arraySize, arrayPosition, Counter = 0;
    
    	LHSEnd = (middle -1);
    	arrayPosition = (LHS);
    
    		while ((LHS <= LHSEnd) && (middle <= RHS)){
    			if (arraySorted[LHS] <= arraySorted[middle]){
    				
    				arrayTemp[arrayPosition] = arraySorted[LHS];
    				arrayPosition = arrayPosition + 1;
    				LHS = LHS + 1;
    
    			}else{
    
    				arrayTemp[arrayPosition] = arraySorted[LHS];
    				arrayPosition = arrayPosition + 1;
    				middle = middle + 1;
    
    			}
    		}
    
    		while(LHS <= LHSEnd){
    			
    			arrayTemp[arrayPosition] = arraySorted[LHS];
    			LHS = LHS + 1;
    			arrayPosition = arrayPosition + 1;
    
    		}
    
    		while(middle <= RHS){
    
    			arrayTemp[arrayPosition] = arraySorted[middle];
    			middle = middle + 1;
    			arrayPosition = arrayPosition + 1;
    		
    		}
    		
    		LHS=-SIZE-1;
    		for(Counter=SIZE;Counter>=0;Counter--){
    			arraySorted[LHS] = arrayTemp[LHS];
    			LHS = LHS + 1;
    		}
    
    }
    Also I am unsure of how to work out the Big-0 or how many procedures it requires to work this out.

    If anyone can help me with either of my problems I would be very grateful.

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Re Big-Oh: work your way through main (should be int main, btw). For each statement, add the Big-Oh orders. When adding them, remember that only the highest one matters.
    For any nested loops, multiply the order.

    For any function calls, calculate the Big-Oh for that function. Then you know that the function call will be of that order.
    Eg, if merge_sort is O^2 and the rest of the code in main is O, then it is O + O^2 = O^2.
    Repeat for ALL functions.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    Registered User
    Join Date
    Mar 2011
    Posts
    2
    Thanks for the insight to Big-Oh: Do you have any idea what is wrong with my script, it just seems to outpute the same array in the same order after 'sort'. Cannot work out why...

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You've got a copy and paste bug here:
    Code:
    				arrayTemp[arrayPosition] = arraySorted[LHS];
    				arrayPosition = arrayPosition + 1;
    				middle = middle + 1;
    I would replace those three lines with just:
    Code:
    arrayTemp[arrayPosition++] = arraySorted[middle++];
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Need a for loop to sort an array
    By lostandconfused in forum C Programming
    Replies: 5
    Last Post: 06-17-2010, 10:15 PM
  3. Replies: 16
    Last Post: 05-29-2009, 07:25 PM
  4. question about multidimensional arrays
    By richdb in forum C Programming
    Replies: 22
    Last Post: 02-26-2006, 09:51 AM
  5. Help with an Array
    By omalleys in forum C Programming
    Replies: 1
    Last Post: 07-01-2002, 08:31 AM

Tags for this Thread