Difference between revisions of "Sorting Arrays"

From CompSciWiki
Jump to: navigation, search
(reverted to previous version some error found)
(moved the intro section above body)
Line 1: Line 1:
 
{{Template:1010Topic
 
{{Template:1010Topic
 
|Chapter_TOC=[[More With Arrays]] > [[Sorting Arrays]]
 
|Chapter_TOC=[[More With Arrays]] > [[Sorting Arrays]]
 +
 +
|Introduction=In 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.
 +
 +
 
|Previous=[[Sorting Arrays]]
 
|Previous=[[Sorting Arrays]]
 
|Next=[[More With Arrays Review Questions and Exercises]]
 
|Next=[[More With Arrays Review Questions and Exercises]]
 
|Body=
 
|Body=
  
−
|Introduction=In 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==
Line 49: Line 50:
  
  
−
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.
+
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.
  
  
Line 61: Line 62:
 
}}
 
}}
  
−
Next, the algorithm will compare the 2nd and 3rd element (|30|20|) and since 30 is larger than 20 the algorithm will swap them.
+
Next, the algorithm will compare the 2nd and 3rd element ({{!}}30{{!}}20{{!}}) and since 30 is larger than 20 the algorithm will swap them.
  
 
<h6>Current Array:</h6>
 
<h6>Current Array:</h6>
Line 74: Line 75:
  
  
−
Next, the 3rd and 4th element will be compared (|30|40|) and since 30 is less than 40 , they won't be swapped.
+
Next, the 3rd and 4th element will be compared ({{!}}30{{!}}40{{!}}) and since 30 is less than 40 , they won't be swapped.
  
  
Line 100: Line 101:
 
}}
 
}}
  
−
Next, the 5th and 6th element will be compared (|60|05|) and since 60 is greater then 05, swap the elements  
+
Next, the 5th and 6th element will be compared ({{!}}60{{!}}05{{!}}) and since 60 is greater then 05, swap the elements  
  
 
<h6>Current Array:</h6>
 
<h6>Current Array:</h6>
Line 112: Line 113:
  
  
−
With each pass the element |05| will move to the front (because it is the smallest element in the array) until no more swapping can take place. At this point the array is sorted.
+
With each pass the element {{!}}05{{!}} will move to the front (because it is the smallest element in the array) until no more swapping can take place. At this point the array is sorted.
  
  
Line 228: Line 229:
  
 
In this section you learned how to sort arrays with two algorithms; Selection Sort and Bubble sort. As you know already there are many more sorting algorithms with different efficiency factors. From the examples above you saw how to sort array of integers, in the future same techniques can be applied to sort arrays with any kind of objects.
 
In this section you learned how to sort arrays with two algorithms; Selection Sort and Bubble sort. As you know already there are many more sorting algorithms with different efficiency factors. From the examples above you saw how to sort array of integers, in the future same techniques can be applied to sort arrays with any kind of objects.
 +
}}

Revision as of 15:11, 6 December 2011

COMP 1010 Home > More With Arrays > Sorting Arrays


Introduction

In 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
Retrieved from "https://hci.cs.umanitoba.ca/mediawiki/index.php?title=Sorting_Arrays&oldid=15739"