Sorting Array's

[ahmed]

Can anyone please write an "easy" tutorial on sorting array's? I have seen some on the internet and read some books but they are too complex for me too understand , so anyone up to make a tutorial ?

[dargueta]

There are many algorithms to do so; the one programmers typically use is called QuickSort or QSort. The easiest, but also probably the slowest sorting algorithm, is the Bubble Sort, which I've implemented to work only on int arrays here:

void bubblesort(int *data,int length)
{
    int swapcount = 1;
    
    while(swapcount > 0)
    {
        swapcount = 0;
        for(int i = 0; i < length - 1; ++i)
        {
            if(data[i] > data[i + 1])
            {
                int temp = data[i];
                data[i] = data[i + 1];
                data[i + 1] = temp;
                ++swapcount;
            }
        }
    }
}

If you don't have to write your own sorting algorithm, just use the C library's qsort(), declared in stdlib.h. You can use it like so:

int compareFunc(const void *a, const void *b)
{
    int *pa = (int *)a, *pb = (int *)b;
    return *pa - *pb;
}

int main()
{
    ....
    qsort(myArray,ARRAY_LENGTH,sizeof(int),compareFunc);
    ....
}

All you need to do is create your own comparison function that takes two const void pointers and returns an int with the following conditions:
1) If the first argument is greater than the second argument, return a positive integer.
2) If the first argument is equal to the second argument, return 0.
3) If the first argument is less than the second argument, return a negative integer.

This can be used to sort structs, classes, anything.

Syntax:
qsort(pointer-to-data,number-of-elements,size-of-element,comparator)

[lucuis]

Try this: Bubble sort tutorial. Hope it is simple enough.

[CPD]

Everyone teaches bubble sort, but I think selection sort is more intuitive. You find the smallest value and move it to the front. Since you moved the smallest value to the front, you can skip that value from that point on. If you do that as if working with the latter portion of the array until the portion dwindles to a length of 1, you end up with a sorted list:

5, 1, 4, 2, 3

Start looking for the smallest value at element 0.
Found the smallest value at element 1.
Swap the values at element 0 and 1.

1, 5, 4, 2, 3

Start looking for the smallest value at element 1 because you already know that the value at element 0 is the smallest in the entire group from 0 to 4.
Found the smallest value at element 3.
Swap the values at element 1 and 3.

1, 2, 4, 5, 3

Start looking for the smallest value at element 2 because you already know that the values up to element 2 are the smallest so far.
Found the smallest value at element 4.
Swap the values at element 2 and 4.

1, 2, 3, 5, 4

Start looking for the smallest value at element 3 because you already know that the values up to element 3 are the smallest so far.
Found the smallest value at element 4.
Swap the values at element 3 and 4.

1, 2, 3, 4, 5

Stop at element 4 because there's only one value left, so it has to be the largest in the array.

Here's some code to play with:

#include <stdio.h>

void printa(int a[], size_t size)
{
  size_t i;

  for (i = 0; i < size; i++)
    printf("%-3d", a[i]);
  puts("");
}

void selection_sort(int a[], size_t size)
{
  size_t i;

  printa(a, size);
  puts("");

  /* From the current unsorted half */
  for (i = 0; i < size - 1; i++) {
    size_t min = i;
    size_t j;

    printf("Start looking for the smallest value at element %d\n", i);

    /* Find the smallest value in the unsorted half */
    for (j = i + 1; j < size; j++)
      if (a[j] < a[min])
        min = j;

    printf("Found the smallest value at element %d\n", min);

    /* Swap the value with the first unsorted value */
    if (min != i) {
      int temp = a[min];
      a[min] = a[i];
      a[i] = temp;

      printf("Swap the values at element %d and %d\n", i, min);
    }
    else
      printf("Don't need to swap because %d is the smallest\n", i);

    puts("");
    printa(a, size);
    puts("");
  }

  printf("Stop at element %d because there's only one value left, "
    "so it has to be the largest in the array\n", i);
}

int main()
{
  int a[] = {0, 1, 9, 2, 8, 3, 7, 4, 6, 5};

  selection_sort(a, 10);

  return 0;
}

[dargueta]

I can see why you'd say the selection sort is more intuitive, and it is - the problem is moving the item to the front. Swapping makes the sort unstable, and shifting is time-consuming.

[CPD]

Swapping makes the sort unstable, and shifting is time-consuming.

That's an interesting statement seeing as you suggested qsort earlier. qsort is pretty much always implemented as quicksort or introsort, and both of those are naturally unstable as well. I wouldn't recommend making selection sort stable anyway because it removes one of the best selling points: super efficient data movement. Selection sorting blows a lot of algorithms away when the values are large and copying is expensive.

Finally, bringing stability into the picture is both unnecessary and counterproductive, since adding another concept just makes things more complicated for ahmed, and he specifically asked for simple. Stability is something that can wait until later.

[dargueta]

True, true. Quicksort can be stable, but like your selection sort, is not stable in efficient implementations. You win.

Ahmed, just ignore what we just said until you really get this.

[ahmed]

Intresting discussion , though where ever I see mostly in books there is bubble sort but y?and I also wanted to discuss that why do we still have to learn C++ ? I really dont find this language intresting but I gota study it cause of my uni I find C# more fun and easier

[WingedPanther]

C++ is used heavily throughout industry. If you look at the list of applications that are created with C++, you will find large segments of the video game industry and MicroSoft near the top of the list. MicroSoft doesn't use C# very much internally, but they want you to use it.

[yuyujoke]

maybe this can help u