Revision as of 20:05, 4 December 2011 (view source) VitaliU (Talk | contribs) ← Older edit		Revision as of 20:09, 4 December 2011 (view source) VitaliU (Talk | contribs) Newer edit →
Line 5:		Line 5:
	|Overview=}}		|Overview=}}
		+
		+	==Bubble Sort==
		+
		+	Selection sorts are used to sort the array into ascending (or descending) order.  The idea behind a selection sort is very simple: iterate through each element in the array, and for each element, look at all remaining elements to see if there is something smaller that should be in this position. If there is, exchange the two values.
		+
		+	Example: sort this array
		+	<pre>
		+	|30|10|20|40|60|
		+	</pre>
		+
		+	1) Outer loop: iterate through each element
		+	<pre>
		+	i = 0 (30)
		+	</pre>
		+
		+	2) Inner loop: iterate through the remaining elements to find a smaller element that should be in this position
		+	<pre>
		+	j = 1 (10)
		+	</pre>
		+
		+	3) Since the element at i is greater than the element at j, swap them - the array will now be:
		+	<pre>
		+	|10|30|20|40|60|
		+	</pre>
		+
		+	4) Again with the inner loop, we will move to the next element and compare:
		+	<pre>
		+	i = 0 (10), j = 2 (20)
		+	</pre>
		+
		+	Since all the other elements in the list are greater than the 0th (10), nothing else will happen for this outer loop.
		+
		+	Loop 2: In the outer loop, we will move to the next element (1) and loop through the remaining elements (starting at 2)
		+	<pre>
		+	i = 1 (30), j = 2(20)
		+	</pre>
		+
		+	Since the element at i is greater than the element at j, swap them and continue, giving us this array (which is now sorted!)
		+	<pre>
		+	|10|20|30|40|60|
		+	</pre>
		+
		+	Here is an example of a very simple selection sorting algorithm:
		+
		+	<pre>
		+	// Selection sort algorithm
		+
		+	public static void selectionSort(int[] haystack) {
		+	for (int i = 0; i < haystack.length - 1; i++) {
		+	for (int j = i + 1; j < haystack.length; j++) {
		+	if (haystack[i] > haystack[j]) {
		+	//... Exchange elements
		+	int temp = haystack[i];
		+	haystack[i] = haystack[j];
		+	haystack[j] = temp;
		+	}
		+	}
		+	}
		+	}
		+	</pre>
	==Selection Sort==		==Selection Sort==

---

Revision as of 20:09, 4 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

Selection sorts are used to sort the array into ascending (or descending) order. The idea behind a selection sort is very simple: iterate through each element in the array, and for each element, look at all remaining elements to see if there is something smaller that should be in this position. If there is, exchange the two values.

Example: sort this array

|30|10|20|40|60|

1) Outer loop: iterate through each element

i = 0 (30)

2) Inner loop: iterate through the remaining elements to find a smaller element that should be in this position

j = 1 (10)

3) Since the element at i is greater than the element at j, swap them - the array will now be:

|10|30|20|40|60|

4) Again with the inner loop, we will move to the next element and compare:

i = 0 (10), j = 2 (20)

Since all the other elements in the list are greater than the 0th (10), nothing else will happen for this outer loop.

Loop 2: In the outer loop, we will move to the next element (1) and loop through the remaining elements (starting at 2)

i = 1 (30), j = 2(20)

Since the element at i is greater than the element at j, swap them and continue, giving us this array (which is now sorted!)

|10|20|30|40|60|

Here is an example of a very simple selection sorting algorithm:

// Selection sort algorithm

public static void selectionSort(int[] haystack) {
    for (int i = 0; i < haystack.length - 1; i++) {
        for (int j = i + 1; j < haystack.length; j++) {
            if (haystack[i] > haystack[j]) {
                //... Exchange elements
                int temp = haystack[i];
                haystack[i] = haystack[j];
                haystack[j] = temp;
            }
        }
    }
}

Selection Sort

Selection sorts are used to sort the array into ascending (or descending) order. The idea behind a selection sort is very simple: iterate through each element in the array, and for each element, look at all remaining elements to see if there is something smaller that should be in this position. If there is, exchange the two values.

Example: sort this array

|30|10|20|40|60|

1) Outer loop: iterate through each element

i = 0 (30)

2) Inner loop: iterate through the remaining elements to find a smaller element that should be in this position

j = 1 (10)

3) Since the element at i is greater than the element at j, swap them - the array will now be:

|10|30|20|40|60|

4) Again with the inner loop, we will move to the next element and compare:

i = 0 (10), j = 2 (20)

Since all the other elements in the list are greater than the 0th (10), nothing else will happen for this outer loop.

Loop 2: In the outer loop, we will move to the next element (1) and loop through the remaining elements (starting at 2)

i = 1 (30), j = 2(20)

Since the element at i is greater than the element at j, swap them and continue, giving us this array (which is now sorted!)

|10|20|30|40|60|

Here is an example of a very simple selection sorting algorithm:

// Selection sort algorithm

public static void selectionSort(int[] haystack) {
    for (int i = 0; i < haystack.length - 1; i++) {
        for (int j = i + 1; j < haystack.length; j++) {
            if (haystack[i] > haystack[j]) {
                //... Exchange elements
                int temp = haystack[i];
                haystack[i] = haystack[j];
                haystack[j] = temp;
            }
        }
    }
}