Need help sorting arrays

**kevinstrijbos** · 01-17-2012

Oh, don't know what algorithm, I just do it my way actually.

Code:

/* AUTH: Kevin Strijbos   DATE: 17/01/2012
   DESCR: includes 2 functions that combine arrays
   */


#include <stdio.h>


#define MAX_LENGTH 10


void initializeArray (int numbers[], int *pointers[]);
void initializeMinima (int *pointers[]);


int main (void)
{
	int numbers[MAX_LENGTH];
	int *pointers[MAX_LENGTH];
	int counter;


	for (counter = 0; counter < MAX_LENGTH ;counter++)
	{
		printf("Give a number:\t\n");
		scanf("%d", &numbers[counter]);
	}


	
	initializeArray(numbers,pointers);


	for (counter = 0; counter < MAX_LENGTH ;counter++)
		printf("Element %d:\t%d\n", counter, *pointers[counter]);


	initializeMinima(pointers);


	printf("-----------------------------------\n");


	for (counter = 0; counter < MAX_LENGTH ;counter++)
		printf("Element %d:\t%d\n", counter, *pointers[counter]);


	return 0;
}


void initializeArray (int numbers[], int *pointers[])
{
	int counter;


	for (counter = 0; counter < MAX_LENGTH ;counter++)
		pointers[counter] = &numbers[counter];
}


void initializeMinima (int *pointers[])
{
	int *temp, index, minima, counter, smallCounter;


	for (counter = 0; counter < MAX_LENGTH - 1 ;counter++)
	{
      minima = *pointers[counter];
      index = counter;


      for (smallCounter = counter + 1; smallCounter < MAX_LENGTH ;smallCounter++)
      {
         if (*pointers[smallCounter] < minima)
         {
            minima = *pointers[counter];
            index = smallCounter;
         }
      }


      /* swapping minima */
      temp = pointers[counter];
      pointers[counter] = pointers[index];
      pointers[index] = temp;      
   }
}

Btw: copied the source code and created a new project, still no errors nor warnings.

**kevinstrijbos** · 01-17-2012

The other student put the swap part in the if test and it worked, maybe that's a clue?

**quzah** · 01-17-2012

Originally Posted by kevinstrijbos

Oh, don't know what algorithm, I just do it my way actually.

Originally Posted by kevinstrijbos

The other student put the swap part in the if test and it worked, maybe that's a clue?

If you don't know how it works, how can you expect to fix it?

Quzah.

**kevinstrijbos** · 01-17-2012

I know how it works, I just don't know how the algorythm's called, nor if it exists. I implemented this method at least 10 times in java and I had no problems with it, worked like a charm.
But what I've figured out till now; if you put the swap part in the if-test in the 2nd for loop (bubble sort), it works. But it really isn't that much of a difference.

Don't know what it is, I'll just use bubble from now on...

**MK27** · 01-17-2012

Oh, don't know what algorithm, I just do it my way actually.

That's what I did the first time I had to sort something too, and it also turned out to be "bubble sort". I was pretty impressed when I saw some of the other ideas people have had thru the years, lol.

Actually, it's not even really bubblesort, because of the inner loop. It's just bubble-esque, and probably even more inefficient (no offence -- I guess that doesn't matter for now).

But since your code does now compile cleanly, time to think about the logic of your algorithm. Can you describe in words what you believe it is supposed to do (like, in detail, pseudocode maybe)?

**kevinstrijbos** · 01-17-2012

To be honest I'm indeed surprised "Aha, I'm not the only one!".

What I want it to do:
I need to found length -1 minimas, so I make a for loop that runs till length - 1 (MAX_LENGTH - 1).
I need to initialise my minimum, so I make the element with index counter the minimum, and I make my index = counter, so I know where my current minimum is.
Next I need to check if there's another number left (one that isn't already "chosen" as a minimum) in my array, so I put up a 2nd counter (smallCounter).
If I find a value smaller than my current minimum, I make that value my minimum and I put smallCounter in "index" (so that I know where my current minimum is...)
When the 2nd loop is finished, I just swap.

I hope my explanation is a little bit clear?

PS: efficiency indeed doesn't matter currently, they just want it to be "clean" code, so that it's easy to read, and I think it's pretty clean since you all can read and understand it

.

**anduril462** · 01-17-2012

Actually, I think your sort most resembles selection sort. You find the smallest element in the list and put it at the beginning. Then you do the same for sub-arrays starting at index 1, 2, 3, ..., n-1. Bubble sort would have the swap inside the inner loop.

**kevinstrijbos** · 01-17-2012

Oh well, all the same for me.

EDIT: Followed the link and it's indeed rather selection sort, and it mostly outperforms bubble sort. Take that MK27! Haha, just joking.

**iMalc** · 01-18-2012

FYI kevinstrijbos, the algorithm you have been using is selection sort.
The inner loop selects the smallest (or largest) item and the outer loop swaps that into the correct place each time.

This is perfectly fine for sorting 10 items. When you need to sort 10000 or more items some day then you'll probably want to look into something better!

**Adak** · 01-18-2012

Selection sort is faster than a crude Bubble sort, but slower than an optimized Bubble sort, or any other (serious) sorting algorithm. It's "claim to fame" is that it will always use the fewest number of swaps of any comparison sorting algorithm.

If you were the Avis parking lot attendant, and your boss said you had to sort all the 1,000 cars parking in the parking lot, you'd definitely want to use the logic from Selection sort. Minimum cost of making comparisons (just glance at the cars), but costly to make the swaps (you need to drive the car from space to space).

Other than that, it's never the best choice for sorting. For a small (less than 100) number of items, especially if it's nearly sorted, Insertion sort rocks. For larger quantities, Shell sort (which is Insertion sort with varying gaps), is quite effective and not complicated. For a large or huge number of items, Quicksort (perhaps optimized with Insertion sort, giving it a nice boost!) and Merge sort, are two of the best sorting algorithms.

Sorting has some wonderful, and well studied algorithms; well worth your studying.

**iMalc** · 01-18-2012

Originally Posted by Adak

Selection If you were the Avis parking lot attendant, and your boss said you had to sort all the 1,000 cars parking in the parking lot, you'd definitely want to use the logic from Selection sort. Minimum cost of making comparisons (just glance at the cars), but costly to make the swaps (you need to drive the car from space to space).

Actually, the option that is the fastest when moving items is hideously expensive would be to use "Exact Sort" whose number of item moves is at most n+1, whereas Selection Sort is up to 3(n-1). (There being 3 moves in a swap)

Other than that, it's never the best choice for sorting. For a small (less than 100) number of items, especially if it's nearly sorted, Insertion sort rocks. For larger quantities, Shell sort (which is Insertion sort with varying gaps), is quite effective and not complicated. For a large or huge number of items, Quicksort (perhaps optimized with Insertion sort, giving it a nice boost!) and Merge sort, are two of the best sorting algorithms.[/QUOTE]Perhaps if you're just sorting ints, but even for small numbers, if the data type is slow to move then selection sort is good.

There's generally about three main classes of sorting algorithm that you ever need, meaning that you can get by with everything just knowing three sorting algorithms:
O(n*n) for when there are very few items
O(n*log n) when there are a lot of items
O(n) for when there are a ridiculously large number of items and the data type allows bucket sorting etc.

**kevinstrijbos** · 01-18-2012

Hmmhmm, but I've heard about something like quantum-sort? It appears that it is O(n), doesn't matter which array?

**KCfromNC** · 01-18-2012

Radix sort and similar are O(n), but they only work for a limited class of inputs (Linear-Time Sorting). And practically speaking, the constant factors ignored by big-O notation seem to matter in their real-world run times.

I'd imagine quantum sorting would be O(1) in time complexity, with some potentially unfortunate implementation details (starting with a total lack of hardware on which to run the algorithm).

Thread: Need help sorting arrays

Thread Tools

Search Thread

Display

Similar Threads

Can i get some help with sorting arrays

Parallel arrays, dynamic memory allocation, and sorting arrays

Sorting Multiple Arrays with complications of 2D arrays and strings.

Help with sorting arrays

Sorting Arrays

Tags for this Thread