Hi can someone plz explain the basics of a bubble sort thank you

Printable View

- 11-27-2001UnregisteredBubble Sort
Hi can someone plz explain the basics of a bubble sort thank you

- 11-27-2001Stoned_Coder
you need two loops

one for the number of passes.

one inside (x) to do one pass

{

is array[x]>array[x+1] if so then swap them else leave them be.

}

number of passes is related to array size-1 - 11-27-2001QuestionC
I will be using the following sequence of numbers...

3 6 8 2 9 0 1 4 7 5

The basic action we're going to is compare two numbers, and if they're out of order, we'll switch them. We're going to do this to every pair of numbers... here's basically how the process goesCode:`3 6 8 2 9 0 1 4`

3 6 8 2 9 0 1 4 (3 & 6, no change)

3 6 8 2 9 0 1 4 (6 & 8, no change)

3 6 2 8 9 0 1 4 (8 & 2, swapped)

3 6 2 8 9 0 1 4 (8 & 9, no change)

3 6 2 8 0 9 1 4 (9 & 0, swapped)

3 6 2 8 0 1 9 4 (9 & 1, swapped)

3 6 2 8 0 1 4 9 (9 & 4, swapped)

Code:`void runThroughList (int a[], int n)`

{

int i, temp;

for (i = 0; i < n - 1; i++)

{

if (a[i] > a[i + 1])

{

// I will refer to the following 3 lines as the swap routine.

temp = a[i];

a[i] = a[i + 1];

a[i + 1] = temp;

}

}

return;

}

3 6 2 8 0 1 4 (9)

So let's look what happens when we keep doing this sort on the left-over part of the array...

3 6 8 2 9 0 1 4

3 6 2 8 0 1 4 (9)

3 2 6 0 1 4 (8) (9)

2 3 0 1 4 (6) (8) (9)

2 0 1 3 (4) (6) (8) (9)

0 1 2 (3) (4) (6) (8) (9)

0 1 (2) (3) (4) (6) (8) (9)

0 (1) (2) (3) (4) (6) (8) (9)

(0) (1) (2) (3) (4) (6) (8) (9)

So, we just have to perform this sort on succesively smaller runs of the array. The code would look like this...Code:`void bubbleSort (int a[], int n)`

{

int i;

for (i = n; i > 0; i--)

{

runThroughList (int a[], int n);

}

return;

}

Code:`void bubbleSort (int a[], int n)`

{

int i, j, temp;

for (i = n; i > 0; i--)

{

for (j = 0; j < i - 1; j++)

{

if (a[j] > a[j + 1])

{

temp = a[j];

a[j] = a[j + 1];

a[j + 1] = temp;

}

}

}

return;

}

An interesting improvement to the bubbleSort function is to make it recognize if the list is sorted on one of it's runs. Notice that in my example, the function could have stopped at

0 1 2 (3) (4) (6) (8) (9)

if it were able to realise this array was already sorted.

Hint: if a list is sorted, then there will be 0 swap routines in runThroughList. - 11-28-2001klausiUse the Quicksort algorithm!
The Quicksort is much faster if you have enough memory!!

klausi