KEMBAR78
Complexity of Simple Sorting Algorithms Bubble Sort | PDF | Mathematical Problem Solving | Areas Of Computer Science
Scribd
Upload
40 views8 pages

Complexity of Simple Sorting Algorithms Bubble Sort

The document discusses the complexity of three simple sorting algorithms: bubble sort, selection sort, and insertion sort. It analyzes the worst-case time complexity of each algorithm through examples and mathematical formulas. The key points are: - Bubble sort has a worst-case time complexity of O(N2) due to making up to N(N-1)/2 comparisons and swaps in each pass through the array. - Selection sort and insertion sort also have O(N2) worst-case time complexity, as they require up to N(N-1)/2 comparisons in the worst case. - While these simple sorting algorithms have quadratic worst-case time complexity, insertion sort has the best average-case

Uploaded by

Venkatakishore Ch
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
40 views8 pages

Complexity of Simple Sorting Algorithms Bubble Sort

The document discusses the complexity of three simple sorting algorithms: bubble sort, selection sort, and insertion sort. It analyzes the worst-case time complexity of each algorithm through examples and mathematical formulas. The key points are: - Bubble sort has a worst-case time complexity of O(N2) due to making up to N(N-1)/2 comparisons and swaps in each pass through the array. - Selection sort and insertion sort also have O(N2) worst-case time complexity, as they require up to N(N-1)/2 comparisons in the worst case. - While these simple sorting algorithms have quadratic worst-case time complexity, insertion sort has the best average-case

Uploaded by

Venkatakishore Ch
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

Complexity of simple sorting algorithms

Bubble sort
23 10 12 5

Bubble sort Selection sort Insertion sort

Bubble sort
23 10 12 5 10 23

Bubble sort
12 5

Bubble sort
10 23 12 5 10 12

Bubble sort
23 5

Bubble sort
10 12 23 5 10 12

Bubble sort
5 23

Bubble sort
10 12 5 23 10 12

Bubble sort
5 23

Bubble sort
10 12 5 23 10 5

Bubble sort
12 23

Bubble sort
10 5 12 23 10 5

Bubble sort
12 23

Bubble sort
5 10 12 23 5 10

Bubble sort
12 23

Complexity of bubble sort

Complexity of bubble sort


c ((N-1) + (N-2) + ... + 1) +k (N-1) + (N-2) + ... + 1 + 1+ 2 + + (N-1) = = N + N + + N = N * (N-1) so our function equals c N*(N-1)/2 + k = 1/2c (N2-N) +k complexity O(N2).

For an array of size N, in the worst case: 1st passage through the inner loop: N-1 comparisons and N-1 swaps ... (N-1)st passage through the inner loop: 1 comparison and 1 swap All together: c ((N-1) + (N-2) + ... + 1) +k where c is the time required to do one comparison and one swap

Complexity of bubble sort


? 1/2c (N2-N) +k <= K* N2 for which values of K and N is this inequality true? For example, K = c+ k and N > 0 (provided N can only take integer values). 23

Selection sort
10 12 5

pos_greatest=0

Selection sort
23 10 12 5 23

Selection sort
10 12 5

pos_greatest=0

pos_greatest=0

Selection sort
23 10 12 5 23

Selection sort
10 12 5

pos_greatest=0

pos_greatest=0 swap(0,3)

Selection sort
5 10 12 23 5

Selection sort
10 12 23

pos_greatest=0 swap(0,3)

pos_greatest=0

Selection sort
5 10 12 23 5

Selection sort
10 12 23

pos_greatest=1

pos_greatest=2 swap(2,2)

Selection sort
5 10 12 23 5

Selection sort
10 12 23

pos_greatest=0

pos_greatest=1 swap(1,1)

Selection sort

Complexity of selection sort


23

10

12

Same number of iterations in the worst case for some different constant c', c' (N2 - N) + k also O(N2)

Insertion Sort
23 10 12 5 23

Insertion Sort
12 5

10

Insertion Sort
23 12 5 10

Insertion Sort
23 12 5

10

Insertion Sort
10 23 5 10

Insertion Sort
23 5

12

12

Insertion Sort
10 12 23 5 10

Insertion Sort
12 23

Insertion Sort
10 12 23 10

Insertion Sort
12 23

Insertion Sort
10 12 23 5

Insertion Sort
10 12 23

Complexity of insertion sort

Reading and informal coursework


In the worst case, has to make N(N-1)/2 comparisons and shifts to the right also O(N2) worst case complexity best case: array already sorted, no shifts.

Shaffer, Chapter 8.1, 8.2. Informal coursework: prove that the simple sorting algorithms above are not in O(N).

You might also like