Subscribe to Stuck in an Infiniteloop        RSS Feed
-----

Let's Sort This Out

Icon Leave Comment
Having lived in the basement of the C/C++ forum for the last few nights, I've noticed an interesting (albeit not new) trend of questions. During the school year there seems to be a heap of sort questions, then programs doing more advanced things, but still needing a sort algorithm, I/O from text files, which then needs to be sorted and around, around we go. So, today I shall cover three sort methods, all of which can be implemented for damn near everything. Bubble Sort, Merge Sort, and Quick Sort.


This Bubble is About to Pop!

Bubble sort is the programmer's bread and butter (well, assuming they like bread and/or butter, but that is a story for another time).

This sort takes an array (or any data structure), iterates through it, checking neighboring values for their value and swaps accordingly. This can go two ways depending if you want ascending or descending values; we'll go with the former:

for (i=0; i<n-1; i++)//how many times to run through the array essentially
{
	for (j=i+1; j<n; j++) // run through the array
	{

		 if (x[i]>x[j])//is the value to the left greater then the one on its immediate right?
		 {//if so
			  temp=x[i]; //temp value equals the index value on the left
			  x[i]=x[j]; //the left now equals the value of the one to its right
			   x[j]=temp; //the right now equals the value of the left
		}
	 }//we continue doing this throughout the array to sort it in ascending order
}



Shazam! Our array is sorted. We can now extract the information we need (lowest, highest, etc...) or display it to the envy of our friends (well....only some of us can do that). This sort method is good for small data structures and in programs where efficiency isn't really a concern or a program due to its small size (that's what the female programmer said).

This Array Merged Into Me on the Interstate!

Next up, my buddy, the merge sort. This one is more efficient then our previous endeavor, especially as the size of the data structure gets infinitely larger. We divide the array in half and then sort each half seperately. We then merge, (aha get it?) them and repeat the process.

// "Main" function of the sequence 
// From here on out everything is called recursively
void mergeSort(int numbers[], int temp[], int array_size)
{
  m_sort(numbers, temp, 0, array_size - 1);
}


void m_sort(int numbers[], int temp[], int left, int right)
{
  int mid;
  //make sure the array has some junk in the trunk
  if (right > left)
  {
	mid = (right + left) / 2;
	m_sort(numbers, temp, left, mid);
	m_sort(numbers, temp, (mid+1), right);

	merge(numbers, temp, left, (mid+1), right);
  }
}

void merge(int numbers[], int temp[], int left, int mid, int right)
{
  int i, left_end, num_elements, tmp_pos;

  left_end = (mid - 1);
  tmp_pos = left;
  num_elements = (right - left + 1);

  while ((left <= left_end) && (mid <= right))
  {
	if (numbers[left] <= numbers[mid])
	{
	  temp[tmp_pos] = numbers[left];
	  tmp_pos += 1;
	  left += 1;
	}
	else
	{
	  temp[tmp_pos] = numbers[mid];
	  tmp_pos += 1;
	  mid += 1;
	}
  }

  while (left <= left_end)
  {
	temp[tmp_pos] = numbers[left];
	left += 1;
	tmp_pos += 1;
  }
  while (mid <= right)
  {
	temp[tmp_pos] = numbers[mid];
	mid += 1;
	tmp_pos += 1;
  }

  for (i=0; i <= num_elements; i++)
  {
	numbers[right] = temp[right];
	right -= 1;
  }
}




Quick! Get Over Here!

Ah the quick sort, another staple in the hearty breakfast that programmers enjoy in the morning. We pick a pivot point, and sort around that value. Quickly that is. Again it is a recursive function which I find more elegant then other possible implementations. Once the array "meets" , it is done and we get to enjoy the fruit of our labors.

int partition(int theList[], int start, int end)
{
	int pivot = theList[end];									   
	int bottom = start-1;												   
	int top = end;														   

	bool notdone = true;
	while (notdone)
	{
		while (notdone)
	{
			bottom += 1;				  

			if (bottom == top)   
		{
				notdone = false;						
				break;
		}
			if (theList[bottom] > pivot)   
		 {
				theList[top] = theList[bottom];	   
				break;
		 }
	}  
	while (notdone)
	{
			top = top-1;					  
			
			if (top == bottom) 
		{
				notdone = false;					  
				break;
		 }
			if (theList[top] < pivot)
		{   
				theList[bottom] = theList[top];
		break;
		 }	  
	}
	}
	theList[top] = pivot;						  
	return top;
}

//Actual function call within program
int quickSort(int theList[], int start, int end)
{
	if (start < end)	 
	{
			 int split = partition(theList, start, end);   //recursion   
			 quickSort(theList, start, split-1);		 
			 quickSort(theList, split+1, end); 
	}
		else
	{
			 return 0;
	}
}




The merge sort and quick sort code can be found under 'my contributions' if you wanted to see the full code lisitng with a main() for example. Thanks for reading dedicated followers. (Do I have any yet?) ;)

--KYA

0 Comments On This Entry

 

February 2020

S M T W T F S
      1
2345678
9101112131415
16171819202122
23242526 27 2829

Tags

    Recent Entries

    Recent Comments

    Search My Blog

    0 user(s) viewing

    0 Guests
    0 member(s)
    0 anonymous member(s)