Sorting

Question 1

What’s Bubble Sort?

sort this using bubble sort: 51428

Answer 1

You compare each element with its neighbors to make sure the smallest value is on the left.

example: Sort 51428

1st: 15428
2nd: 14528
3rd: 14258
4th: 12458

it takes 4 iterations and the final sort is 12458/

Question 2

What is Selection Sort?

sort this using the selection sort: 063210798

Answer 2

you swap the minimum value in the list with the order of index

example: Sort 063210798

1st: 063210798
index (0)
2nd: 023610798
index (0)(1)
3rd: 023610798
index (0)(1)(2)
4th: 023610798
index (0)(1)(2)(3)
5th: 023671098
index (0)(1)(2)(3)(4)
6th: 023678910
index (0)(1)(2)(3)(4)(5)

Question 3

What is Insertion Sort?

sort this using the insertion sort: 063210798

Answer 3

swap with elements to its left and keep comparing the same number with previous values till it’s the smallest one (aka the longest time complexity)

example: Sort 063210798
1st: [0, 6, 3, 2, 10, 7, 9, 8] (0 is already less than 6, so no change)
2nd: [0, 3, 6, 2, 10, 7, 9, 8]
3rd: [0, 3, 6, 2, 10, 7, 9, 8]
4th: [0, 2, 3, 6, 10, 7, 9, 8]
5th: [0, 2, 3, 6, 7, 10, 9, 8]
6th: [0, 2, 3, 6, 7, 9, 10, 8]
7th: [0, 2, 3, 6, 7, 8, 9, 10]

** ps an iteration is counted once it is position in its right position, no the amount of times it swaps with other numbers.

Question 4

What is Merge Sort?

sort this using the Merge sort: 063210798

Answer 4

You split the array into to groups and sort them individually in a pair of 2 and then merge them together.

Example: 063210798
Initial Array: [0, 6, 3, 2, 10, 7, 9, 8]

Divide:

Divide the array into two halves: [0, 6, 3, 2] and [10, 7, 9, 8].
Divide Sub-arrays:

Divide [0, 6, 3, 2] into [0, 6] and [3, 2].
Divide [10, 7, 9, 8] into [10, 7] and [9, 8].
Conquer:

Sort each sub-array:
[0, 6] → [0, 6]
[3, 2] → [2, 3]
[10, 7] → [7, 10]
[9, 8] → [8, 9]
Combine:

Merge the sorted sub-arrays:
Merge [0, 6] and [2, 3] → [0, 2, 3, 6]
Merge [7, 10] and [8, 9] → [7, 8, 9, 10]
Combine the Final Arrays:

Merge the two sorted halves [0, 2, 3, 6] and [7, 8, 9, 10] to get the final sorted array [0, 2, 3, 6, 7, 8, 9, 10].
So, the sorted array using Merge Sort is [0, 2, 3, 6, 7, 8, 9, 10].

Question 5

What is Heap Sort?

Sort 285391 using Heap Sort:

Answer 5

You make a tree that turns original list to a max heap list that has the highest number from top to bottom and left to right. Then you switch from least num to top with a high number extract the maximum element from the heap and go back to max heap list and keep rebuilding the heap until all elements are sorted.

Example:
Step 1: Convert the array into a max heap.
Heap: 9
/ \
8 5
/ \ / \
3 2 1

Step 2: Extract 9 and swap with 1
Heap: 1
/ \
8 5
/ \ / \
3 2 9

put 9 at the end of new sorted list

Step 3: Extract 8 and swap with 1
Heap: 8
/ \
1 5
/ \ / \
3 2
list now: 89

Step 3: switch 3 and swap with 1
Heap: 8
/ \
3 5
/ \ / \
1 2
* remember you need to keep high to low tree

Step 4: Extract 5 and swap with 3
Heap: 5
/ \
3
/ \
1 2
list now: 589

Step 5: Extract 3 and swap with 1
Heap:
3
/ \
1 2
list now: 3589

Step 5: switch 2 with 1
Heap:
1
\
2
Step 5: Extract 2 and swap with 1
Heap:
2
\
1
list now: 23589

left now is 1 and you extract that and put current so:

123589