Overview of Sorting Algorithms

Sorting Lesson
CS1313 Spring 2024
1
Sorting Lesson Outline
1.
Sorting Lesson Outline
2.
How to Sort an Array?
3.
Many Sorting Algorithms
4.
Bubble Sort #1
5.
Bubble Sort #2
6.
Bubble Sort #3
7.
Bubble Sort #4
8.
Bubble Sort #5
9.
Bubble Sort Run Start
10.
Bubble Sort Run Iteration #1
11.
Bubble Sort Run Iteration #2
12.
Bubble Sort Run Iteration #3
13.
Bubble Sort Run Iteration #4
14.
Bubble Sort Run Iteration #5
15.
Bubble Sort Run Iteration #6
16.
Bubble Sort Run Iteration #7
17.
Bubble Sort Run Iteration #8
18.
Bubble Sort Run End
19.
Time Complexity of Bubble Sort #1
20.
Time Complexity of Bubble Sort #2
21.
Selection Sort
22.
Selection Sort #1
23.
Selection Sort #2
24.
Selection Sort Run Start
25.
Selection Sort Run Minimum #1
26.
Selection Sort Run Minimum #2
27.
Selection Sort Run Minimum #3
28.
Selection Sort Run Minimum #4
29.
Selection Sort Run Minimum #5
30.
Selection Sort Run Minimum #6
31.
Selection Sort Run Minimum #7
32.
Selection Sort Run Minimum #8
33.
Selection Sort Run End
34.
Time Complexity of Selection Sort #1
35.
Time Complexity of Selection Sort #2
36.
Quick Sort #1
37.
Quick Sort #2
38.
Quick Sort #3
39.
Quick Sort #4
40.
Quick Sort #5
41.
Quick Sort Run Start
42.
Quick Sort Run Call: low 0, high 8
43.
Quick Sort Run Call: low 0, high 3
44.
Quick Sort Run Call: low 2, high 3
45.
Quick Sort Run Call: low 0, high 3 End
46.
Quick Sort Run Call: low 5, high 8
47.
Quick Sort Run Call: low 5, high 6
48.
Quick Sort Run Call: low 7, high 8
49.
Quick Sort Run Call: low 5, high 8 End
50.
Quick Sort Run Call: low 0, high 8 End
51.
Quick Sort Run End
52.
Time Complexity of Quick Sort #1
53.
Time Complexity of Quick Sort #2
Sorting Lesson
CS1313 Spring 2024
2
How to Sort an Array?
Suppose you have a big array full of data, and you want to put
it into order, either from lowest to highest (ascending) or
highest to lowest (descending).
How can you sort it so that it’s in the order you want?
Sorting Lesson
CS1313 Spring 2024
3
Many Sorting Algorithms
There are many sorting algorithms, for example:
Bubble Sort
Selection Sort
Quick Sort
… and many more.
Sorting Lesson
CS1313 Spring 2024
4
Bubble Sort #1
#include <stdio.h>
int main ()
{ /* main */
    const int minimum_length       =  1;
    const int first_element        =  0;
    const int program_failure_code = -1;
    const int program_success_code =  0;
    int* array = (int*)NULL;
    int length, element;
    void bubble_sort(int* array, int length);
    void print_array(int* array, int length);
http://en.wikipedia.org/wiki/Bubble_sort
Sorting Lesson
CS1313 Spring 2024
5
Bubble Sort #2
    printf("I'm going to sort an array for you.\n");
    printf("How many elements will the array have?\n");
    scanf("%d", &length);
    if (length < minimum_length) {
        printf("ERROR: can't have an array of length %d.\n",
            length);
        exit(program_failure_code);
    } /* if (length < minimum_length) */
    array = (int*)malloc(sizeof(int) * length);
    if (array == (int*)NULL) {
        printf("ERROR: can't allocate an array of length %d.\n",
            length);
        exit(program_failure_code);
    } /* if (array == (int*)NULL) */
    printf("What are the %d elements, unsorted?\n", length);
    for (element = first_element; element < length; element++) {
        scanf("%d", &array[element]);
    } /* for element */
    bubble_sort(array, length);
    printf("The %d elements, sorted, are:\n", length);
    print_array(array, length);
    return program_success_code;
} /* main */
Sorting Lesson
CS1313 Spring 2024
6
Bubble Sort #3
void bubble_sort (int* array, int length)
{ /* bubble_sort */
    const int  first_element   = 0;
    const int  first_iteration = 0;
    const char false           = 0;
    const char true            = 1;
    int  temporary;
    int  element;
    int  iteration;
    char this_iteration_had_a_swap; /* Boolean */
    void print_array(int* array, int length);
Sorting Lesson
CS1313 Spring 2024
7
Bubble Sort #4
    iteration = first_iteration;
    this_iteration_had_a_swap = true;
    while (this_iteration_had_a_swap) {
        printf("\n");
        this_iteration_had_a_swap = false;
        for (element = first_element;
             element < (length - 1); element++) {
            if (array[element] > array[element + 1]) {
                /* Swap! */
                temporary          = array[element];
                array[element]     = array[element + 1];
                array[element + 1] = temporary;
                this_iteration_had_a_swap = true;
            } /* if (array[ element ] > array[ element + 1 ]) */
            printf("After iteration #%d", iteration);
            printf(" comparing elements #%d/%d:\n",
                element, element + 1);
            print_array(array, length);
        } /* for element */
        iteration++;
    } /* while (this_iteration_had_a_swap) */
} /* bubble_sort */
Sorting Lesson
CS1313 Spring 2024
8
Bubble Sort #5
void print_array (int* array, int length)
{ /* print_array */
    const int  first_element =  0;
    int element;
    for (element = first_element; element < length; element++) {
        printf("%d ", array[element]);
    } /* for element */
    printf("\n");
} /* print_array */
Sorting Lesson
CS1313 Spring 2024
9
Bubble Sort Run Start
% 
bubblesort
I'm going to sort an array for you.
How many elements will the array have?
9
What are the 9 elements, unsorted?
-23  97  18  21   5 -86  64   0 -37
Sorting Lesson
CS1313 Spring 2024
10
Bubble Sort Run Iteration #1
After iteration #1 comparing elements #0/1:
-23  97  18  21   5 -86  64   0 -37
After iteration #1 comparing elements #1/2:
-23  18  97  21   5 -86  64   0 -37
After iteration #1 comparing elements #2/3:
-23  18  21  97   5 -86  64   0 -37
After iteration #1 comparing elements #3/4:
-23  18  21   5  97 -86  64   0 -37
After iteration #1 comparing elements #4/5:
-23  18  21   5 -86  97  64   0 -37
After iteration #1 comparing elements #5/6:
-23  18  21   5 -86  64  97   0 -37
After iteration #1 comparing elements #6/7:
-23  18  21   5 -86  64   0  97 -37
After iteration #1 comparing elements #7/8:
-23  18  21   5 -86  64   0 -37  97
Biggest!
Sorting Lesson
CS1313 Spring 2024
11
Bubble Sort Run Iteration #2
After iteration #2 comparing elements #0/1:
-23  18  21   5 -86  64   0 -37  97
After iteration #2 comparing elements #1/2:
-23  18  21   5 -86  64   0 -37  97
After iteration #2 comparing elements #2/3:
-23  18   5  21 -86  64   0 -37  97
After iteration #2 comparing elements #3/4:
-23  18   5 -86  21  64   0 -37  97
After iteration #2 comparing elements #4/5:
-23  18   5 -86  21  64   0 -37  97
After iteration #2 comparing elements #5/6:
-23  18   5 -86  21   0  64 -37  97
After iteration #2 comparing elements #6/7:
-23  18   5 -86  21   0 -37  64  97
After iteration #2 comparing elements #7/8:
-23  18   5 -86  21   0 -37  64  97
Second
biggest!
Sorting Lesson
CS1313 Spring 2024
12
Bubble Sort Run Iteration #3
After iteration #3 comparing elements #0/1:
-23  18   5 -86  21   0 -37  64  97
After iteration #3 comparing elements #1/2:
-23   5  18 -86  21   0 -37  64  97
After iteration #3 comparing elements #2/3:
-23   5 -86  18  21   0 -37  64  97
After iteration #3 comparing elements #3/4:
-23   5 -86  18  21   0 -37  64  97
After iteration #3 comparing elements #4/5:
-23   5 -86  18   0  21 -37  64  97
After iteration #3 comparing elements #5/6:
-23   5 -86  18   0 -37  21  64  97
After iteration #3 comparing elements #6/7:
-23   5 -86  18   0 -37  21  64  97
After iteration #3 comparing elements #7/8:
-23   5 -86  18   0 -37  21  64  97
Sorting Lesson
CS1313 Spring 2024
13
Bubble Sort Run Iteration #4
After iteration #4 comparing elements #0/1:
-23   5 -86  18   0 -37  21  64  97
After iteration #4 comparing elements #1/2:
-23 -86   5  18   0 -37  21  64  97
After iteration #4 comparing elements #2/3:
-23 -86   5  18   0 -37  21  64  97
After iteration #4 comparing elements #3/4:
-23 -86   5   0  18 -37  21  64  97
After iteration #4 comparing elements #4/5:
-23 -86   5   0 -37  18  21  64  97
After iteration #4 comparing elements #5/6:
-23 -86   5   0 -37  18  21  64  97
After iteration #4 comparing elements #6/7:
-23 -86   5   0 -37  18  21  64  97
After iteration #4 comparing elements #7/8:
-23 -86   5   0 -37  18  21  64  97
Sorting Lesson
CS1313 Spring 2024
14
Bubble Sort Run Iteration #5
After iteration #5 comparing elements #0/1:
-86 -23   5   0 -37  18  21  64  97
After iteration #5 comparing elements #1/2:
-86 -23   5   0 -37  18  21  64  97
After iteration #5 comparing elements #2/3:
-86 -23   0   5 -37  18  21  64  97
After iteration #5 comparing elements #3/4:
-86 -23   0 -37   5  18  21  64  97
After iteration #5 comparing elements #4/5:
-86 -23   0 -37   5  18  21  64  97
After iteration #5 comparing elements #5/6:
-86 -23   0 -37   5  18  21  64  97
After iteration #5 comparing elements #6/7:
-86 -23   0 -37   5  18  21  64  97
After iteration #5 comparing elements #7/8:
-86 -23   0 -37   5  18  21  64  97
Sorting Lesson
CS1313 Spring 2024
15
Bubble Sort Run Iteration #6
After iteration #6 comparing elements #0/1:
-86 -23   0 -37   5  18  21  64  97
After iteration #6 comparing elements #1/2:
-86 -23   0 -37   5  18  21  64  97
After iteration #6 comparing elements #2/3:
-86 -23 -37   0   5  18  21  64  97
After iteration #6 comparing elements #3/4:
-86 -23 -37   0   5  18  21  64  97
After iteration #6 comparing elements #4/5:
-86 -23 -37   0   5  18  21  64  97
After iteration #6 comparing elements #5/6:
-86 -23 -37   0   5  18  21  64  97
After iteration #6 comparing elements #6/7:
-86 -23 -37   0   5  18  21  64  97
After iteration #6 comparing elements #7/8:
-86 -23 -37   0   5  18  21  64  97
Sorting Lesson
CS1313 Spring 2024
16
Bubble Sort Run Iteration #7
After iteration #7 comparing elements #0/1:
-86 -23 -37   0   5  18  21  64  97
After iteration #7 comparing elements #1/2:
-86 -37 -23   0   5  18  21  64  97
After iteration #7 comparing elements #2/3:
-86 -37 -23   0   5  18  21  64  97
After iteration #7 comparing elements #3/4:
-86 -37 -23   0   5  18  21  64  97
After iteration #7 comparing elements #4/5:
-86 -37 -23   0   5  18  21  64  97
After iteration #7 comparing elements #5/6:
-86 -37 -23   0   5  18  21  64  97
After iteration #7 comparing elements #6/7:
-86 -37 -23   0   5  18  21  64  97
After iteration #7 comparing elements #7/8:
-86 -37 -23   0   5  18  21  64  97
Sorting Lesson
CS1313 Spring 2024
17
Bubble Sort Run Iteration #8
After iteration #8 comparing elements #0/1:
-86 -37 -23   0   5  18  21  64  97
After iteration #8 comparing elements #1/2:
-86 -37 -23   0   5  18  21  64  97
After iteration #8 comparing elements #2/3:
-86 -37 -23   0   5  18  21  64  97
After iteration #8 comparing elements #3/4:
-86 -37 -23   0   5  18  21  64  97
After iteration #8 comparing elements #4/5:
-86 -37 -23   0   5  18  21  64  97
After iteration #8 comparing elements #5/6:
-86 -37 -23   0   5  18  21  64  97
After iteration #8 comparing elements #6/7:
-86 -37 -23   0   5  18  21  64  97
After iteration #8 comparing elements #7/8:
-86 -37 -23   0   5  18  21  64  97
Nothing
got
swapped,
so done!
Sorting Lesson
CS1313 Spring 2024
18
Bubble Sort Run End
The 9 elements, sorted, are:
-86 -37 -23   0   5  18  21  64  97
Sorting Lesson
CS1313 Spring 2024
19
Time Complexity of Bubble Sort #1
    iteration = first_iteration;
    this_iteration_had_a_swap = true;
    while (this_iteration_had_a_swap) {
        printf("\n");
        this_iteration_had_a_swap = false;
        for (element = first_element;
             element < (length - 1); element++) {
            if (array[element] > array[element + 1]) {
                /* Swap! */
                temporary          = array[element];
                array[element]     = array[element + 1];
                array[element + 1] = temporary;
                this_iteration_had_a_swap = true;
            } /* if (array[ element ] > array[ element + 1 ]) */
            printf("After iteration #%d", iteration);
            printf(" comparing elements #%d/%d:\n",
                element, element + 1);
            print_array(array, length);
        } /* for element */
        iteration++;
    } /* while (this_iteration_had_a_swap) */
} /* bubble_sort */
Sorting Lesson
CS1313 Spring 2024
20
Time Complexity of Bubble Sort #2
What is the time complexity of bubble sort?
Suppose the array has length 
n
.
Well, the inner 
for
 loop always has 
n
-1 iterations.
How many iterations does the outer 
while
 loop have?
Well, the outer loop will iterate until the whole array is sorted
(plus one extra iteration to determine that it 
is
 sorted).
On average, it’ll have to do that about ½
 
n
 times.
Therefore, the time complexity is 
O
(
n
2
) – which is 
BAD
.
Sorting Lesson
CS1313 Spring 2024
21
Selection Sort
Selection sort works by selecting the lowest (or highest) value
in the list and swapping it with the first (or last) element,
then finding the second lowest (or highest) and swapping it
with the second (or next-to-last) element, and so on.
http://en.wikipedia.org/wiki/Selection_sort
Sorting Lesson
CS1313 Spring 2024
22
Selection Sort #1
void selection_sort (int* array, int length)
{ /* selection_sort */
    const int  first_element = 0;
    int temporary;
    int element1, element2, minimum_element;
    void print_array(int* array, int length);
Sorting Lesson
CS1313 Spring 2024
23
Selection Sort #2
    for (element1 = first_element;
         element1 < (length - 1); element1++) {
        /* Find the minimum. */
        minimum_element = element1;
        for (element2 = element1 + 1;
             element2 < length; element2++) {
            if (array[element2] < array[minimum_element]) {
                minimum_element = element2;
            } /* if (array[element2] < array[minimum_element]) */
            printf("Element %d is %d, minimum element at %d is %d.\n",
                element2, array[element2],
                minimum_element, array[minimum_element]);
        } /* for element2 */
        /* Swap! */
        temporary              = array[element1];
        array[element1]        = array[minimum_element];
        array[minimum_element] = temporary;
        printf("Minimum #%d had index %d",
            element1 + 1, minimum_element);
        printf(" but now has index %d:\n", element1);
        print_array(array, length);
    } /* for element1 */
} /* selection_sort */
Sorting Lesson
CS1313 Spring 2024
24
Selection Sort Run Start
I'm going to sort an array for you.
How many elements will the array have?
9
What are the 9 elements, unsorted?
-23  97  18  21   5 -86  64   0 -37
Sorting Lesson
CS1313 Spring 2024
25
Selection Sort Run Minimum #1
-23  97  18  21   5 -86  64   0 -37
Element 1 is 97, minimum element at 0 is -23.
Element 2 is 18, minimum element at 0 is -23.
Element 3 is 21, minimum element at 0 is -23.
Element 4 is 5, minimum element at 0 is -23.
Element 5 is -86, minimum element at 5 is -86.
Element 6 is 64, minimum element at 5 is -86.
Element 7 is 0, minimum element at 5 is -86.
Element 8 is -37, minimum element at 5 is -86.
Minimum #1 had index 5 but now has index 0:
-86  97  18  21   5 -23  64   0 -37
Sorting Lesson
CS1313 Spring 2024
26
Selection Sort Run Minimum #2
-86  97  18  21   5 -23  64   0 -37
Element 2 is 18, minimum element at 2 is 18.
Element 3 is 21, minimum element at 2 is 18.
Element 4 is 5, minimum element at 4 is 5.
Element 5 is -23, minimum element at 5 is -23.
Element 6 is 64, minimum element at 5 is -23.
Element 7 is 0, minimum element at 5 is -23.
Element 8 is -37, minimum element at 8 is -37.
Minimum #2 had index 8 but now has index 1:
-86 -37  18  21   5 -23  64   0  97
Sorting Lesson
CS1313 Spring 2024
27
Selection Sort Run Minimum #3
-86 -37  18  21   5 -23  64   0  97
Element 3 is 21, minimum element at 2 is 18.
Element 4 is 5, minimum element at 4 is 5.
Element 5 is -23, minimum element at 5 is -23.
Element 6 is 64, minimum element at 5 is -23.
Element 7 is 0, minimum element at 5 is -23.
Element 8 is 97, minimum element at 5 is -23.
Minimum #3 had index 5 but now has index 2:
-86 -37 -23  21   5  18  64   0  97
Sorting Lesson
CS1313 Spring 2024
28
Selection Sort Run Minimum #4
-86 -37 -23  21   5  18  64   0  97
Element 4 is 5, minimum element at 4 is 5.
Element 5 is 18, minimum element at 4 is 5.
Element 6 is 64, minimum element at 4 is 5.
Element 7 is 0, minimum element at 7 is 0.
Element 8 is 97, minimum element at 7 is 0.
Minimum #4 had index 7 but now has index 3:
-86 -37 -23   0   5  18  64  21  97
Sorting Lesson
CS1313 Spring 2024
29
Selection Sort Run Minimum #5
-86 -37 -23   0   5  18  64  21  97
Element 5 is 18, minimum element at 4 is 5.
Element 6 is 64, minimum element at 4 is 5.
Element 7 is 21, minimum element at 4 is 5.
Element 8 is 97, minimum element at 4 is 5.
Minimum #5 had index 4 but now has index 4:
-86 -37 -23   0   5  18  64  21  97
Sorting Lesson
CS1313 Spring 2024
30
Selection Sort Run Minimum #6
-86 -37 -23   0   5  18  64  21  97
Element 6 is 64, minimum element at 5 is 18.
Element 7 is 21, minimum element at 5 is 18.
Element 8 is 97, minimum element at 5 is 18.
Minimum #6 had index 5 but now has index 5:
-86 -37 -23   0   5  18  64  21  97
Sorting Lesson
CS1313 Spring 2024
31
Selection Sort Run Minimum #7
-86 -37 -23   0   5  18  64  21  97
Element 7 is 21, minimum element at 7 is 21.
Element 8 is 97, minimum element at 7 is 21.
Minimum #7 had index 7 but now has index 6:
-86 -37 -23   0   5  18  21  64  97
Sorting Lesson
CS1313 Spring 2024
32
Selection Sort Run Minimum #8
-86 -37 -23   0   5  18  21  64  97
Element 8 is 97, minimum element at 7 is 64.
Minimum #8 had index 7 but now has index 7:
-86 -37 -23   0   5  18  21  64  97
Sorting Lesson
CS1313 Spring 2024
33
Selection Sort Run End
The 9 elements, sorted, are:
-86 -37 -23   0   5  18  21  64  97
Sorting Lesson
CS1313 Spring 2024
34
Time Complexity of Selection Sort #1
    for (element1 = first_element;
         element1 < (length - 1); element1++) {
        /* Find the minimum. */
        minimum_element = element1;
        for (element2 = element1 + 1;
             element2 < length; element2++) {
            if (array[element2] < array[minimum_element]) {
                minimum_element = element2;
            } /* if (array[element2] < array[minimum_element]) */
        } /* for element2 */
        /* Swap! */
        temporary              = array[element1];
        array[element1]        = array[minimum_element];
        array[minimum_element] = temporary;
        printf("Minimum #%d had index %d",
            element1, minimum_element);
        printf(" but now has index %d:\n", element1);
        print_array(array, length);
    } /* for element1 */
} /* selection_sort */
Sorting Lesson
CS1313 Spring 2024
35
Time Complexity of Selection Sort #2
What is the time complexity of selection sort?
Suppose the array has length 
n
.
Well, the outer 
for
 loop always has 
n
-1 iterations.
How many iterations does the inner 
for
 loop have?
Well, for the first iteration of the outer loop, the inner loop has
n
-1 iterations; for the second iteration of the outer loop, the
inner loop has 
n
-2 iterations; and so on.
On average, the inner loop will have approximately ½
 
n
iterations.
Therefore, the time complexity is 
O
(
n
2
) – which is 
BAD
.
Sorting Lesson
CS1313 Spring 2024
36
Quick Sort #1
void quicksort (int* array, int length)
{ /* quicksort */
    void quicksort_helper(int* array, int length,
                          int low, int high);
    quicksort_helper(array, length, 0, length - 1);
} /* quicksort */
http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm
Sorting Lesson
CS1313 Spring 2024
37
Quick Sort #2
void quicksort_helper (int* array, int length, int low, int high)
{ /* quicksort_helper */
    int temporary;
    int element1, element2, middle;
    int pivot;
    void print_array(int* array, int length);
    element1 = low;
    element2 = high;
    middle   = (low + high) / 2;
    pivot    = array[middle];
Sorting Lesson
CS1313 Spring 2024
38
Quick Sort #3
 /* Partition this part of the array into halves. */
    do {
        while (array[element1] < pivot) {
            element1++;
            printf("low %d, high %d, pivot %d, element1 %d\n",
                low, high, pivot, element1);
            print_array(array, length);
        } /* while (array[element1] < pivot) */
        while (array[element2] > pivot) {
            element2--;
            printf("low %d, high %d, pivot %d, element2 %d\n",
                low, high, pivot, element2);
            print_array(array, length);
        } /* while (array[element2] > pivot) */
Sorting Lesson
CS1313 Spring 2024
39
Quick Sort #4
       /* Now, all values at indices between element1
        * and element2 are in the wrong place. */
        if (element1 <= element2) {
            /* Swap! */
            temporary       = array[element1];
            array[element1] = array[element2];
            array[element2] = temporary;
            element1++;
            element2--;
            printf("low %d, high %d, pivot %d,",
                low, high, pivot);
            printf(" element1 %d, element2 %d:\n",
                element1, element2);
            print_array(array, length);
        } /* if (element1 <= element2) */
    } while (element1 <= element2);
Sorting Lesson
CS1313 Spring 2024
40
Quick Sort #5
   /* Recursively sort the two halves. */
    if (low < element2) {
        quicksort_helper(array, length, low, element2);
    } /* if (low < element2) */
    if (element1 < high) {
       quicksort_helper(array, length, element1, high);
    } /* if (element1 < high) */
    printf("After sorting, %d through %d is:\n",
        low, high);
    print_array(array, length);
} /* quicksort_helper */
Sorting Lesson
CS1313 Spring 2024
41
Quick Sort Run Start
I'm going to sort an array for you.
How many elements will the array have?
9
What are the 9 elements, unsorted?
-23  97  18  21   5 -86  64   0 -37
Sorting Lesson
CS1313 Spring 2024
42
Quick Sort Run Call: low 0, high 8
-23  97  18  21   5 -86  64   0 -37
low 0, high 8, pivot 5, element1 1
-23  97  18  21   5 -86  64   0 -37
low 0, high 8, pivot 5, element1 2, element2 7:
-23 -37  18  21   5 -86  64   0  97
low 0, high 8, pivot 5, element1 3, element2 6:
-23 -37   0  21   5 -86  64  18  97
low 0, high 8, pivot 5, element2 5
-23 -37   0  21   5 -86  64  18  97
low 0, high 8, pivot 5, element1 4, element2 4:
-23 -37   0 -86   5  21  64  18  97
low 0, high 8, pivot 5, element1 5, element2 3:
-23 -37   0 -86   5  21  64  18  97
Sorting Lesson
CS1313 Spring 2024
43
Quick Sort Run Call: low 0, high 3
-23 -37   0 -86   5  21  64  18  97
low 0, high 3, pivot -37, element1 1, element2 2:
-86 -37   0 -23   5  21  64  18  97
low 0, high 3, pivot -37, element2 1
-86 -37   0 -23   5  21  64  18  97
low 0, high 3, pivot -37, element1 2, element2 0:
-86 -37   0 -23   5  21  64  18  97
Sorting Lesson
CS1313 Spring 2024
44
Quick Sort Run Call: low 2, high 3
-86 -37   0 -23   5  21  64  18  97
low 2, high 3, pivot 0, element1 3, element2 2:
-86 -37 -23   0   5  21  64  18  97
After sorting, 2 through 3 is:
-86 -37 -23   0   5  21  64  18  97
Sorting Lesson
CS1313 Spring 2024
45
Quick Sort Run Call: low 0, high 3 End
After sorting, 0 through 3 is:
-86 -37 -23   0   5  21  64  18  97
Sorting Lesson
CS1313 Spring 2024
46
Quick Sort Run Call: low 5, high 8
-86 -37 -23   0   5  21  64  18  97
low 5, high 8, pivot 64, element1 6
-86 -37 -23   0   5  21  64  18  97
low 5, high 8, pivot 64, element2 7
-86 -37 -23   0   5  21  64  18  97
low 5, high 8, pivot 64, element1 7, element2 6:
-86 -37 -23   0   5  21  18  64  97
Sorting Lesson
CS1313 Spring 2024
47
Quick Sort Run Call: low 5, high 6
-86 -37 -23   0   5  21  18  64  97
low 5, high 6, pivot 21, element1 6, element2 5:
-86 -37 -23   0   5  18  21  64  97
After sorting, 5 through 6 is:
-86 -37 -23   0   5  18  21  64  97
Sorting Lesson
CS1313 Spring 2024
48
Quick Sort Run Call: low 7, high 8
-86 -37 -23   0   5  18  21  64  97
low 7, high 8, pivot 64, element2 7
-86 -37 -23   0   5  18  21  64  97
low 7, high 8, pivot 64, element1 8, element2 6:
-86 -37 -23   0   5  18  21  64  97
After sorting, 7 through 8 is:
-86 -37 -23   0   5  18  21  64  97
Sorting Lesson
CS1313 Spring 2024
49
Quick Sort Run Call: low 5, high 8 End
After sorting, 5 through 8 is:
-86 -37 -23   0   5  18  21  64  97
Sorting Lesson
CS1313 Spring 2024
50
Quick Sort Run Call: low 0, high 8 End
After sorting, 0 through 8 is:
-86 -37 -23   0   5  18  21  64  97
Sorting Lesson
CS1313 Spring 2024
51
Quick Sort Run End
The 9 elements, sorted, are:
-86 -37 -23   0   5  18  21  64  97
Sorting Lesson
CS1313 Spring 2024
52
Time Complexity of Quick Sort #1
What is the time complexity of quick sort?
Suppose the array has length 
n
.
Well, each call to 
quicksort_helper
 cuts the array in half.
But, each call to 
quicksort_helper
 can be accompanied
by another call that covers the other half of the current
subarray.
So, at each level of calls, most of the array gets visited.
So all we need to know is, how many levels of calls are there?
Sorting Lesson
CS1313 Spring 2024
53
Time Complexity of Quick Sort #2
At each level of calls, the entire array gets visited.
All we need to know is, how many levels of calls are there?
It turns out that, for an array of length 
n
, there are 
O
(log
 
n
)
levels.
So the total time complexity is 
O
(
n
 
log
 
n
) – it’s 
quick
!

								

								

								

										

												
Slide Note

												

										

								


								
						

							
						


							

								

									
										
Embed
									
									
										
Share
									

									
									
									

								

								
							


							

							 
 							 
 							 
						  


							
							

								
Explore the world of sorting algorithms through a detailed lesson outline covering popular methods like Bubble Sort, Selection Sort, and Quick Sort. Learn how to sort an array, understand the time complexity of different sorting techniques, and discover the intricacies of implementation through code snippets and visual aids.


								
    
																		
  •   Sorting Algorithms
    • 
																	
  •    Bubble Sort
    • 
																	
  •    Selection Sort
    • 
																	
  •    Quick Sort
    • 
																	
  •    Sorting Lesson
    • 
																

								

								

									

										pulling_t
										

											 pulling_t Follow
											

										

									

									
Uploaded on Sep 26, 2024 | 0 Views

								

								


								

									
Download Presentation

									
								

								
Please find below an Image/Link to download the presentation.

								
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.


									
									

									


										 
										 
										 
										 

									

									

									

								
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

								

									 
									
Download Presentation
								

								
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.


								

									
 E N D 

								


							
Presentation Transcript

							

							
  1. Sorting Lesson Outline 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. Sorting Lesson Outline How to Sort an Array? Many Sorting Algorithms Bubble Sort #1 Bubble Sort #2 Bubble Sort #3 Bubble Sort #4 Bubble Sort #5 Bubble Sort Run Start Bubble Sort Run Iteration #1 Bubble Sort Run Iteration #2 Bubble Sort Run Iteration #3 Bubble Sort Run Iteration #4 Bubble Sort Run Iteration #5 Bubble Sort Run Iteration #6 Bubble Sort Run Iteration #7 Bubble Sort Run Iteration #8 Bubble Sort Run End Time Complexity of Bubble Sort #1 Time Complexity of Bubble Sort #2 Selection Sort Selection Sort #1 Selection Sort #2 Selection Sort Run Start Selection Sort Run Minimum #1 Selection Sort Run Minimum #2 Selection Sort Run Minimum #3 Selection Sort Run Minimum #4 Selection Sort Run Minimum #5 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. Selection Sort Run Minimum #6 Selection Sort Run Minimum #7 Selection Sort Run Minimum #8 Selection Sort Run End Time Complexity of Selection Sort #1 Time Complexity of Selection Sort #2 Quick Sort #1 Quick Sort #2 Quick Sort #3 Quick Sort #4 Quick Sort #5 Quick Sort Run Start Quick Sort Run Call: low 0, high 8 Quick Sort Run Call: low 0, high 3 Quick Sort Run Call: low 2, high 3 Quick Sort Run Call: low 0, high 3 End Quick Sort Run Call: low 5, high 8 Quick Sort Run Call: low 5, high 6 Quick Sort Run Call: low 7, high 8 Quick Sort Run Call: low 5, high 8 End Quick Sort Run Call: low 0, high 8 End Quick Sort Run End Time Complexity of Quick Sort #1 Time Complexity of Quick Sort #2 Sorting Lesson CS1313 Spring 2024 1
    2. 
            
            
            
  2. How to Sort an Array? -23 97 18 21 5 -86 64 0 -37 Suppose you have a big array full of data, and you want to put  it into order, either from lowest to highest (ascending) or  highest to lowest (descending). How can you sort it so that it   s in the order you want? Sorting Lesson CS1313 Spring 2024 2
    3. 
            
            
            
  3. Many Sorting Algorithms There are many sorting algorithms, for example:     Bubble Sort     Selection Sort     Quick Sort     and many more. Sorting Lesson CS1313 Spring 2024 3
    4. 
            
            
            
  4. Bubble Sort #1 #include <stdio.h> int main () { /* main */     const int minimum_length       =  1;     const int first_element        =  0;     const int program_failure_code = -1;     const int program_success_code =  0;     int* array = (int*)NULL;     int length, element;     void bubble_sort(int* array, int length);     void print_array(int* array, int length); http://en.wikipedia.org/wiki/Bubble_sort Sorting Lesson CS1313 Spring 2024 4
    5. 
            
            
            
  5. Bubble Sort #2 printf("I'm going to sort an array for you.\n");     printf("How many elements will the array have?\n");     scanf("%d", &length);     if (length < minimum_length) {         printf("ERROR: can't have an array of length %d.\n",             length);         exit(program_failure_code);     } /* if (length < minimum_length) */     array = (int*)malloc(sizeof(int) * length);     if (array == (int*)NULL) {         printf("ERROR: can't allocate an array of length %d.\n",             length);         exit(program_failure_code);     } /* if (array == (int*)NULL) */     printf("What are the %d elements, unsorted?\n", length);     for (element = first_element; element < length; element++) {         scanf("%d", &array[element]);     } /* for element */     bubble_sort(array, length);     printf("The %d elements, sorted, are:\n", length);     print_array(array, length);     return program_success_code; } /* main */ Sorting Lesson CS1313 Spring 2024 5
    6. 
            
            
            
  6. Bubble Sort #3 void bubble_sort (int* array, int length) { /* bubble_sort */     const int  first_element   = 0;     const int  first_iteration = 0;     const char false           = 0;     const char true            = 1;     int  temporary;     int  element;     int  iteration;     char this_iteration_had_a_swap; /* Boolean */     void print_array(int* array, int length); Sorting Lesson CS1313 Spring 2024 6
    7. 
            
            
            
  7. Bubble Sort #4 iteration = first_iteration;     this_iteration_had_a_swap = true;     while (this_iteration_had_a_swap) {         printf("\n");         this_iteration_had_a_swap = false;         for (element = first_element;              element < (length - 1); element++) {             if (array[element] > array[element + 1]) {                 /* Swap! */                 temporary          = array[element];                 array[element]     = array[element + 1];                 array[element + 1] = temporary;                 this_iteration_had_a_swap = true;             } /* if (array[ element ] > array[ element + 1 ]) */             printf("After iteration #%d", iteration);             printf(" comparing elements #%d/%d:\n",                 element, element + 1);             print_array(array, length);         } /* for element */         iteration++;     } /* while (this_iteration_had_a_swap) */ } /* bubble_sort */ Sorting Lesson CS1313 Spring 2024 7
    8. 
            
            
            
  8. Bubble Sort #5 void print_array (int* array, int length) { /* print_array */     const int  first_element =  0;     int element;     for (element = first_element; element < length; element++) {         printf("%d ", array[element]);     } /* for element */     printf("\n"); } /* print_array */ Sorting Lesson CS1313 Spring 2024 8
    9. 
            
            
            
  9. Bubble Sort Run Start % bubblesort I'm going to sort an array for you. How many elements will the array have? 9 What are the 9 elements, unsorted? -23  97  18  21   5 -86  64   0 -37 Sorting Lesson CS1313 Spring 2024 9
    10. 
            
            
            
  10. Bubble Sort Run Iteration #1 After iteration #1 comparing elements #0/1: -23  97  18  21   5 -86  64   0 -37 After iteration #1 comparing elements #1/2: -23  18  97  21   5 -86  64   0 -37 After iteration #1 comparing elements #2/3: -23  18  21  97   5 -86  64   0 -37 After iteration #1 comparing elements #3/4: -23  18  21   5  97 -86  64   0 -37 After iteration #1 comparing elements #4/5: -23  18  21   5 -86  97  64   0 -37 After iteration #1 comparing elements #5/6: -23  18  21   5 -86  64  97   0 -37 After iteration #1 comparing elements #6/7: -23  18  21   5 -86  64   0  97 -37 After iteration #1 comparing elements #7/8: -23  18  21   5 -86  64   0 -37  97 Biggest! Sorting Lesson CS1313 Spring 2024 10
    11. 
            
            
            
  11. Bubble Sort Run Iteration #2 After iteration #2 comparing elements #0/1: -23  18  21   5 -86  64   0 -37  97 After iteration #2 comparing elements #1/2: -23  18  21   5 -86  64   0 -37  97 After iteration #2 comparing elements #2/3: -23  18   5  21 -86  64   0 -37  97 After iteration #2 comparing elements #3/4: -23  18   5 -86  21  64   0 -37  97 After iteration #2 comparing elements #4/5: -23  18   5 -86  21  64   0 -37  97 After iteration #2 comparing elements #5/6: -23  18   5 -86  21   0  64 -37  97 After iteration #2 comparing elements #6/7: -23  18   5 -86  21   0 -37  64  97 After iteration #2 comparing elements #7/8: -23  18   5 -86  21   0 -37  64  97 Second  biggest! Sorting Lesson CS1313 Spring 2024 11
    12. 
            
            
            
  12. Bubble Sort Run Iteration #3 After iteration #3 comparing elements #0/1: -23  18   5 -86  21   0 -37  64  97 After iteration #3 comparing elements #1/2: -23   5  18 -86  21   0 -37  64  97 After iteration #3 comparing elements #2/3: -23   5 -86  18  21   0 -37  64  97 After iteration #3 comparing elements #3/4: -23   5 -86  18  21   0 -37  64  97 After iteration #3 comparing elements #4/5: -23   5 -86  18   0  21 -37  64  97 After iteration #3 comparing elements #5/6: -23   5 -86  18   0 -37  21  64  97 After iteration #3 comparing elements #6/7: -23   5 -86  18   0 -37  21  64  97 After iteration #3 comparing elements #7/8: -23   5 -86  18   0 -37  21  64  97 Sorting Lesson CS1313 Spring 2024 12
    13. 
            
            
            
  13. Bubble Sort Run Iteration #4 After iteration #4 comparing elements #0/1: -23   5 -86  18   0 -37  21  64  97 After iteration #4 comparing elements #1/2: -23 -86   5  18   0 -37  21  64  97 After iteration #4 comparing elements #2/3: -23 -86   5  18   0 -37  21  64  97 After iteration #4 comparing elements #3/4: -23 -86   5   0  18 -37  21  64  97 After iteration #4 comparing elements #4/5: -23 -86   5   0 -37  18  21  64  97 After iteration #4 comparing elements #5/6: -23 -86   5   0 -37  18  21  64  97 After iteration #4 comparing elements #6/7: -23 -86   5   0 -37  18  21  64  97 After iteration #4 comparing elements #7/8: -23 -86   5   0 -37  18  21  64  97 Sorting Lesson CS1313 Spring 2024 13
    14. 
            
            
            
  14. Bubble Sort Run Iteration #5 After iteration #5 comparing elements #0/1: -86 -23   5   0 -37  18  21  64  97 After iteration #5 comparing elements #1/2: -86 -23   5   0 -37  18  21  64  97 After iteration #5 comparing elements #2/3: -86 -23   0   5 -37  18  21  64  97 After iteration #5 comparing elements #3/4: -86 -23   0 -37   5  18  21  64  97 After iteration #5 comparing elements #4/5: -86 -23   0 -37   5  18  21  64  97 After iteration #5 comparing elements #5/6: -86 -23   0 -37   5  18  21  64  97 After iteration #5 comparing elements #6/7: -86 -23   0 -37   5  18  21  64  97 After iteration #5 comparing elements #7/8: -86 -23   0 -37   5  18  21  64  97 Sorting Lesson CS1313 Spring 2024 14
    15. 
            
            
            
  15. Bubble Sort Run Iteration #6 After iteration #6 comparing elements #0/1: -86 -23   0 -37   5  18  21  64  97 After iteration #6 comparing elements #1/2: -86 -23   0 -37   5  18  21  64  97 After iteration #6 comparing elements #2/3: -86 -23 -37   0   5  18  21  64  97 After iteration #6 comparing elements #3/4: -86 -23 -37   0   5  18  21  64  97 After iteration #6 comparing elements #4/5: -86 -23 -37   0   5  18  21  64  97 After iteration #6 comparing elements #5/6: -86 -23 -37   0   5  18  21  64  97 After iteration #6 comparing elements #6/7: -86 -23 -37   0   5  18  21  64  97 After iteration #6 comparing elements #7/8: -86 -23 -37   0   5  18  21  64  97 Sorting Lesson CS1313 Spring 2024 15
    16. 
            
            
            
  16. Bubble Sort Run Iteration #7 After iteration #7 comparing elements #0/1: -86 -23 -37   0   5  18  21  64  97 After iteration #7 comparing elements #1/2: -86 -37 -23   0   5  18  21  64  97 After iteration #7 comparing elements #2/3: -86 -37 -23   0   5  18  21  64  97 After iteration #7 comparing elements #3/4: -86 -37 -23   0   5  18  21  64  97 After iteration #7 comparing elements #4/5: -86 -37 -23   0   5  18  21  64  97 After iteration #7 comparing elements #5/6: -86 -37 -23   0   5  18  21  64  97 After iteration #7 comparing elements #6/7: -86 -37 -23   0   5  18  21  64  97 After iteration #7 comparing elements #7/8: -86 -37 -23   0   5  18  21  64  97 Sorting Lesson CS1313 Spring 2024 16
    17. 
            
            
            
  17. Bubble Sort Run Iteration #8 After iteration #8 comparing elements #0/1: -86 -37 -23   0   5  18  21  64  97 After iteration #8 comparing elements #1/2: -86 -37 -23   0   5  18  21  64  97 After iteration #8 comparing elements #2/3: -86 -37 -23   0   5  18  21  64  97 After iteration #8 comparing elements #3/4: -86 -37 -23   0   5  18  21  64  97 After iteration #8 comparing elements #4/5: -86 -37 -23   0   5  18  21  64  97 After iteration #8 comparing elements #5/6: -86 -37 -23   0   5  18  21  64  97 After iteration #8 comparing elements #6/7: -86 -37 -23   0   5  18  21  64  97 After iteration #8 comparing elements #7/8: -86 -37 -23   0   5  18  21  64  97 Nothing  got  swapped,  so done! Sorting Lesson CS1313 Spring 2024 17
    18. 
            
            
            
  18. Bubble Sort Run End The 9 elements, sorted, are: -86 -37 -23   0   5  18  21  64  97 Sorting Lesson CS1313 Spring 2024 18
    19. 
            
            
            
  19. Time Complexity of Bubble Sort #1 iteration = first_iteration;     this_iteration_had_a_swap = true;     while (this_iteration_had_a_swap) {         printf("\n");         this_iteration_had_a_swap = false;         for (element = first_element;              element < (length - 1); element++) {             if (array[element] > array[element + 1]) {                 /* Swap! */                 temporary          = array[element];                 array[element]     = array[element + 1];                 array[element + 1] = temporary;                 this_iteration_had_a_swap = true;             } /* if (array[ element ] > array[ element + 1 ]) */             printf("After iteration #%d", iteration);             printf(" comparing elements #%d/%d:\n",                 element, element + 1);             print_array(array, length);         } /* for element */         iteration++;     } /* while (this_iteration_had_a_swap) */ } /* bubble_sort */ Sorting Lesson CS1313 Spring 2024 19
    20. 
            
            
            
  20. Time Complexity of Bubble Sort #2 What is the time complexity of bubble sort? Suppose the array has length n. Well, the inner for loop always has n-1 iterations. How many iterations does the outer while loop have? Well, the outer loop will iterate until the whole array is sorted  (plus one extra iteration to determine that it is sorted). On average, it   ll have to do that about   n times. Therefore, the time complexity is O(n2)     which is BAD. Sorting Lesson CS1313 Spring 2024 20
    21. 
            
            
            
  21. Selection Sort Selection sort works by selecting the lowest (or highest) value  in the list and swapping it with the first (or last) element,  then finding the second lowest (or highest) and swapping it  with the second (or next-to-last) element, and so on. http://en.wikipedia.org/wiki/Selection_sort Sorting Lesson CS1313 Spring 2024 21
    22. 
            
            
            
  22. Selection Sort #1 void selection_sort (int* array, int length) { /* selection_sort */     const int  first_element = 0;     int temporary;     int element1, element2, minimum_element;     void print_array(int* array, int length); Sorting Lesson CS1313 Spring 2024 22
    23. 
            
            
            
  23. Selection Sort #2 for (element1 = first_element;          element1 < (length - 1); element1++) {         /* Find the minimum. */         minimum_element = element1;         for (element2 = element1 + 1;              element2 < length; element2++) {             if (array[element2] < array[minimum_element]) {                 minimum_element = element2;             } /* if (array[element2] < array[minimum_element]) */             printf("Element %d is %d, minimum element at %d is %d.\n",                 element2, array[element2],                 minimum_element, array[minimum_element]);         } /* for element2 */         /* Swap! */         temporary              = array[element1];         array[element1]        = array[minimum_element];         array[minimum_element] = temporary;         printf("Minimum #%d had index %d",             element1 + 1, minimum_element);         printf(" but now has index %d:\n", element1);         print_array(array, length);     } /* for element1 */ } /* selection_sort */ Sorting Lesson CS1313 Spring 2024 23
    24. 
            
            
            
  24. Selection Sort Run Start I'm going to sort an array for you. How many elements will the array have? 9 What are the 9 elements, unsorted? -23  97  18  21   5 -86  64   0 -37 Sorting Lesson CS1313 Spring 2024 24
    25. 
            
            
            
  25. Selection Sort Run Minimum #1 -23  97  18  21   5 -86  64   0 -37 Element 1 is 97, minimum element at 0 is -23. Element 2 is 18, minimum element at 0 is -23. Element 3 is 21, minimum element at 0 is -23. Element 4 is 5, minimum element at 0 is -23. Element 5 is -86, minimum element at 5 is -86. Element 6 is 64, minimum element at 5 is -86. Element 7 is 0, minimum element at 5 is -86. Element 8 is -37, minimum element at 5 is -86. Minimum #1 had index 5 but now has index 0: -86  97  18  21   5 -23  64   0 -37 Sorting Lesson CS1313 Spring 2024 25
    26. 
            
            
            
  26. Selection Sort Run Minimum #2 -86  97  18  21   5 -23  64   0 -37 Element 2 is 18, minimum element at 2 is 18. Element 3 is 21, minimum element at 2 is 18. Element 4 is 5, minimum element at 4 is 5. Element 5 is -23, minimum element at 5 is -23. Element 6 is 64, minimum element at 5 is -23. Element 7 is 0, minimum element at 5 is -23. Element 8 is -37, minimum element at 8 is -37. Minimum #2 had index 8 but now has index 1: -86 -37  18  21   5 -23  64   0  97 Sorting Lesson CS1313 Spring 2024 26
    27. 
            
            
            
  27. Selection Sort Run Minimum #3 -86 -37  18  21   5 -23  64   0  97 Element 3 is 21, minimum element at 2 is 18. Element 4 is 5, minimum element at 4 is 5. Element 5 is -23, minimum element at 5 is -23. Element 6 is 64, minimum element at 5 is -23. Element 7 is 0, minimum element at 5 is -23. Element 8 is 97, minimum element at 5 is -23. Minimum #3 had index 5 but now has index 2: -86 -37 -23  21   5  18  64   0  97 Sorting Lesson CS1313 Spring 2024 27
    28. 
            
            
            
  28. Selection Sort Run Minimum #4 -86 -37 -23  21   5  18  64   0  97 Element 4 is 5, minimum element at 4 is 5. Element 5 is 18, minimum element at 4 is 5. Element 6 is 64, minimum element at 4 is 5. Element 7 is 0, minimum element at 7 is 0. Element 8 is 97, minimum element at 7 is 0. Minimum #4 had index 7 but now has index 3: -86 -37 -23   0   5  18  64  21  97 Sorting Lesson CS1313 Spring 2024 28
    29. 
            
            
            
  29. Selection Sort Run Minimum #5 -86 -37 -23   0   5  18  64  21  97 Element 5 is 18, minimum element at 4 is 5. Element 6 is 64, minimum element at 4 is 5. Element 7 is 21, minimum element at 4 is 5. Element 8 is 97, minimum element at 4 is 5. Minimum #5 had index 4 but now has index 4: -86 -37 -23   0   5  18  64  21  97 Sorting Lesson CS1313 Spring 2024 29
    30. 
            
            
            
  30. Selection Sort Run Minimum #6 -86 -37 -23   0   5  18  64  21  97 Element 6 is 64, minimum element at 5 is 18. Element 7 is 21, minimum element at 5 is 18. Element 8 is 97, minimum element at 5 is 18. Minimum #6 had index 5 but now has index 5: -86 -37 -23   0   5  18  64  21  97 Sorting Lesson CS1313 Spring 2024 30
    31. 
            
            
            
  31. Selection Sort Run Minimum #7 -86 -37 -23   0   5  18  64  21  97 Element 7 is 21, minimum element at 7 is 21. Element 8 is 97, minimum element at 7 is 21. Minimum #7 had index 7 but now has index 6: -86 -37 -23   0   5  18  21  64  97 Sorting Lesson CS1313 Spring 2024 31
    32. 
            
            
            
  32. Selection Sort Run Minimum #8 -86 -37 -23   0   5  18  21  64  97 Element 8 is 97, minimum element at 7 is 64. Minimum #8 had index 7 but now has index 7: -86 -37 -23   0   5  18  21  64  97 Sorting Lesson CS1313 Spring 2024 32
    33. 
            
            
            
  33. Selection Sort Run End The 9 elements, sorted, are: -86 -37 -23   0   5  18  21  64  97 Sorting Lesson CS1313 Spring 2024 33
    34. 
            
            
            
  34. Time Complexity of Selection Sort #1 for (element1 = first_element;          element1 < (length - 1); element1++) {         /* Find the minimum. */         minimum_element = element1;         for (element2 = element1 + 1;              element2 < length; element2++) {             if (array[element2] < array[minimum_element]) {                 minimum_element = element2;             } /* if (array[element2] < array[minimum_element]) */         } /* for element2 */         /* Swap! */         temporary              = array[element1];         array[element1]        = array[minimum_element];         array[minimum_element] = temporary;         printf("Minimum #%d had index %d",             element1, minimum_element);         printf(" but now has index %d:\n", element1);         print_array(array, length);     } /* for element1 */ } /* selection_sort */ Sorting Lesson CS1313 Spring 2024 34
    35. 
            
            
            
  35. Time Complexity of Selection Sort #2 What is the time complexity of selection sort? Suppose the array has length n. Well, the outer for loop always has n-1 iterations. How many iterations does the inner for loop have? Well, for the first iteration of the outer loop, the inner loop has  n-1 iterations; for the second iteration of the outer loop, the  inner loop has n-2 iterations; and so on. On average, the inner loop will have approximately   n iterations. Therefore, the time complexity is O(n2)     which is BAD. Sorting Lesson CS1313 Spring 2024 35
    36. 
            
            
            
  36. Quick Sort #1 void quicksort (int* array, int length) { /* quicksort */     void quicksort_helper(int* array, int length,                           int low, int high);     quicksort_helper(array, length, 0, length - 1); } /* quicksort */ http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm Sorting Lesson CS1313 Spring 2024 36
    37. 
            
            
            
  37. Quick Sort #2 void quicksort_helper (int* array, int length, int low, int high) { /* quicksort_helper */     int temporary;     int element1, element2, middle;     int pivot;     void print_array(int* array, int length);     element1 = low;     element2 = high;     middle   = (low + high) / 2;     pivot    = array[middle]; Sorting Lesson CS1313 Spring 2024 37
    38. 
            
            
            
  38. Quick Sort #3 /* Partition this part of the array into halves. */     do {         while (array[element1] < pivot) {             element1++;             printf("low %d, high %d, pivot %d, element1 %d\n",                 low, high, pivot, element1);             print_array(array, length);         } /* while (array[element1] < pivot) */         while (array[element2] > pivot) {             element2--;             printf("low %d, high %d, pivot %d, element2 %d\n",                 low, high, pivot, element2);             print_array(array, length);         } /* while (array[element2] > pivot) */ Sorting Lesson CS1313 Spring 2024 38
    39. 
            
            
            
  39. Quick Sort #4 /* Now, all values at indices between element1         * and element2 are in the wrong place. */         if (element1 <= element2) {             /* Swap! */             temporary       = array[element1];             array[element1] = array[element2];             array[element2] = temporary;             element1++;             element2--;             printf("low %d, high %d, pivot %d,",                 low, high, pivot);             printf(" element1 %d, element2 %d:\n",                 element1, element2);             print_array(array, length);         } /* if (element1 <= element2) */     } while (element1 <= element2); Sorting Lesson CS1313 Spring 2024 39
    40. 
            
            
            
  40. Quick Sort #5 /* Recursively sort the two halves. */     if (low < element2) {         quicksort_helper(array, length, low, element2);     } /* if (low < element2) */     if (element1 < high) {        quicksort_helper(array, length, element1, high);     } /* if (element1 < high) */     printf("After sorting, %d through %d is:\n",         low, high);     print_array(array, length); } /* quicksort_helper */ Sorting Lesson CS1313 Spring 2024 40
    41. 
            
            
            
  41. Quick Sort Run Start I'm going to sort an array for you. How many elements will the array have? 9 What are the 9 elements, unsorted? -23  97  18  21   5 -86  64   0 -37 Sorting Lesson CS1313 Spring 2024 41
    42. 
            
            
            
  42. Quick Sort Run Call: low 0, high 8 -23  97  18  21   5 -86  64   0 -37 low 0, high 8, pivot 5, element1 1 -23  97  18  21   5 -86  64   0 -37 low 0, high 8, pivot 5, element1 2, element2 7: -23 -37  18  21   5 -86  64   0  97 low 0, high 8, pivot 5, element1 3, element2 6: -23 -37   0  21   5 -86  64  18  97 low 0, high 8, pivot 5, element2 5 -23 -37   0  21   5 -86  64  18  97 low 0, high 8, pivot 5, element1 4, element2 4: -23 -37   0 -86   5  21  64  18  97 low 0, high 8, pivot 5, element1 5, element2 3: -23 -37   0 -86   5  21  64  18  97 Sorting Lesson CS1313 Spring 2024 42
    43. 
            
            
            
  43. Quick Sort Run Call: low 0, high 3 -23 -37   0 -86   5  21  64  18  97 low 0, high 3, pivot -37, element1 1, element2 2: -86 -37   0 -23   5  21  64  18  97 low 0, high 3, pivot -37, element2 1 -86 -37   0 -23   5  21  64  18  97 low 0, high 3, pivot -37, element1 2, element2 0: -86 -37   0 -23   5  21  64  18  97 Sorting Lesson CS1313 Spring 2024 43
    44. 
            
            
            
  44. Quick Sort Run Call: low 2, high 3 -86 -37   0 -23   5  21  64  18  97 low 2, high 3, pivot 0, element1 3, element2 2: -86 -37 -23   0   5  21  64  18  97 After sorting, 2 through 3 is: -86 -37 -23   0   5  21  64  18  97 Sorting Lesson CS1313 Spring 2024 44
    45. 
            
            
            
  45. Quick Sort Run Call: low 0, high 3 End After sorting, 0 through 3 is: -86 -37 -23   0   5  21  64  18  97 Sorting Lesson CS1313 Spring 2024 45
    46. 
            
            
            
  46. Quick Sort Run Call: low 5, high 8 -86 -37 -23   0   5  21  64  18  97 low 5, high 8, pivot 64, element1 6 -86 -37 -23   0   5  21  64  18  97 low 5, high 8, pivot 64, element2 7 -86 -37 -23   0   5  21  64  18  97 low 5, high 8, pivot 64, element1 7, element2 6: -86 -37 -23   0   5  21  18  64  97 Sorting Lesson CS1313 Spring 2024 46
    47. 
            
            
            
  47. Quick Sort Run Call: low 5, high 6 -86 -37 -23   0   5  21  18  64  97 low 5, high 6, pivot 21, element1 6, element2 5: -86 -37 -23   0   5  18  21  64  97 After sorting, 5 through 6 is: -86 -37 -23   0   5  18  21  64  97 Sorting Lesson CS1313 Spring 2024 47
    48. 
            
            
            
  48. Quick Sort Run Call: low 7, high 8 -86 -37 -23   0   5  18  21  64  97 low 7, high 8, pivot 64, element2 7 -86 -37 -23   0   5  18  21  64  97 low 7, high 8, pivot 64, element1 8, element2 6: -86 -37 -23   0   5  18  21  64  97 After sorting, 7 through 8 is: -86 -37 -23   0   5  18  21  64  97 Sorting Lesson CS1313 Spring 2024 48
    49. 
            
            
            
  49. Quick Sort Run Call: low 5, high 8 End After sorting, 5 through 8 is: -86 -37 -23   0   5  18  21  64  97 Sorting Lesson CS1313 Spring 2024 49
    50. 
            
            
            
  50. Quick Sort Run Call: low 0, high 8 End After sorting, 0 through 8 is: -86 -37 -23   0   5  18  21  64  97 Sorting Lesson CS1313 Spring 2024 50
    51. 
            
            
            
						

						

					

					
					
					

						
Related

						

						


							
							
							
							

						

							

									

      

        
          

            

              BD FACS Aria III for Efficient Cell Sorting
            

            

              
BD FACS Aria III for Efficient Cell Sorting

              
rocco

            

          

        
      


     

      

        
          

            

              Food Processing Operations: Cleaning, Sorting, and Grading
            

            

              
Food Processing Operations: Cleaning, Sorting, and Grading

              
talia

            

          

        
      


     

      

        
          

            

              Sorting Algorithms: Bubble Sort and Insertion Sort
            

            

              
Sorting Algorithms: Bubble Sort and Insertion Sort

              
lars

            

          

        
      


     

      

        
          

            

              Sorting Algorithms in Data Structures
            

            

              
Sorting Algorithms in Data Structures

              
yohan

            

          

        
      


     

      

        
          

            

              Combining Graph Algorithms with Data Structures and Algorithms in CSE 373 by Kasey Champion
            

            

              
Combining Graph Algorithms with Data Structures and Algorithms in CSE 373 by Kasey Champion

              
maliyah

            

          

        
      


     

      

        
          

            

              Sorting Techniques in Data Structures
            

            

              
Sorting Techniques in Data Structures

              
natan

            

          

        
      


     

      

        
          

            

              Sorting Techniques: Complexity, Stability, and Cases
            

            

              
Sorting Techniques: Complexity, Stability, and Cases

              
jazlyn

            

          

        
      


     

      

        
          

            

              Randomized Algorithms: A Deep Dive into Las Vegas and Monte Carlo Algorithms
            

            

              
Randomized Algorithms: A Deep Dive into Las Vegas and Monte Carlo Algorithms

              
nieve

            

          

        
      


     

      

        
          

            

              SQL Tips to Enhance Data Sorting Techniques
            

            

              
SQL Tips to Enhance Data Sorting Techniques

              
hafsah

            

          

        
      


     

      

        
          

            

              Sorting Algorithms for Efficient Data Management
            

            

              
Sorting Algorithms for Efficient Data Management

              
anav_203

            

          

        
      


     

      

        
          

            

              Heapsort and Heaps: A Generic Algorithm for Sorting
            

            

              
Heapsort and Heaps: A Generic Algorithm for Sorting

              
chines

            

          

        
      


     

      

        
          

            

              Comprehensive Overview of Sorting Algorithms in Computer Science
            

            

              
Comprehensive Overview of Sorting Algorithms in Computer Science

              
edem_3

            

          

        
      


     

      

        
          

            

              Parallel Sorting Algorithms and Amdahl's Law
            

            

              
Parallel Sorting Algorithms and Amdahl's Law

              
kay_xav

            

          

        
      


     

      

        
          

            

              Overview of Sorting Algorithms in Data Structures
            

            

              
Overview of Sorting Algorithms in Data Structures

              
ktabo

            

          

        
      


     

      

        
          

            

              Salinity in Seawater: Density, Composition, and Variations
            

            

              
Salinity in Seawater: Density, Composition, and Variations

              
kyliann

            

          

        
      


     

      

        
          

            

              CSE 373: Data Structures and Algorithms Overview
            

            

              
CSE 373: Data Structures and Algorithms Overview

              
hkat

            

          

        
      


     

      

        
          

            

              Divide and Conquer Sorting at Otterbein University
            

            

              
Divide and Conquer Sorting at Otterbein University

              
mish_3

            

          

        
      


     

      

        
          

            

              Algorithms and Sorting Methods
            

            

              
Algorithms and Sorting Methods

              
wass_iya

            

          

        
      


     

      

        
          

            

              Sorting Algorithms in Computer Science
            

            

              
Sorting Algorithms in Computer Science

              
beck_208

            

          

        
      


     

      

        
          

            

              Overview of Sorting Algorithms and Quadratic Sorting - CS 330 Lecture Notes
            

            

              
Overview of Sorting Algorithms and Quadratic Sorting - CS 330 Lecture Notes

              
aubreya

            

          

        
      


     

      

        
          

            

              Efficient Setup and Maintenance for Sorting Process
            

            

              
Efficient Setup and Maintenance for Sorting Process

              
lleas

            

          

        
      


     

      

        
          

            

              Introduction to Basic Algorithms: Searching and Sorting
            

            

              
Introduction to Basic Algorithms: Searching and Sorting

              
leda_66

            

          

        
      


     							

						

					

					

				


				

			

		
		

			

				
				

					
More Related Content

					

						

														

					

				

				
			

		












 





  
  
  



giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#