Sorting Arrays
COMP 1010 Home > More With Arrays > Sorting Arrays
IntroductionIn the previous section we learned how to search an array, but there is a requirement that the array will be sorted. In this chapter we are going to cover sorting algorithms to sort arrays, although there are number of sorting algorithms with different" time complexity ", the most common ones are Selection sort and bubble sort.
|
---|
Bubble Sort
Bubble sort is an easy algorithm to master when learning sorting arrays. This algorithm called bubble sort since it takes the larger elements "bubbles" and put them at the end of the array with each pass. Bubble sort compares each time two elements and if they are not in order swapping them.Next the algorithm compares next set of elements, this process continues until there is no more items to swap.
Pseudo code:
procedure bubbleSort( A : list of sortable items ) repeat swapped = false for i = 1 to length(A) - 1 inclusive do: if A[i-1] > A[i] then swap( A[i-1], A[i] ) swapped = true end if end for until not swapped end procedure
Let's look at an example.Lets sort the following array:
|30|10|20|40|60|05|
When the bubble sort algorithm starts, it will compare the first two elements |30|10| and it will swap them since 30 larger then 10.
Current Array
|10|30|20|40|60|05|
Next, the algorithm will compare the 2nd and 3rd element (|30|20|) and since 30 is larger than 20 the algorithm will swap them.
Current Array:
|10|20|30|40|60|05|
Next, the 3rd and 4th element will be compared (|30|40|) and since 30 is less than 40 , they won't be swapped.
Current Array:
|10|20|30|40|60|05|
Now the 4th element will be compared with the 5th element (
Previous Page: Sorting Arrays | Next Page: More With Arrays Review Questions and Exercises |