For c programming: Can someone help explain the difference between bubble sort a
ID: 3668784 • Letter: F
Question
For c programming:
Can someone help explain the difference between bubble sort and exchange sort?
I've come up with the following differences.
Bubble sort looks for the highest number and puts it in its correct spot, and then looks for next highest number on next pass etc.
Bubble sort compares each element to element beside it
I think I'm mainly confused with the process of bubble sort. Is it comparing each number (with its neighbor) and swapping until it reaches a higher number?
vs.
Exchange sort looks for the smallest number and puts it in its correct spot, and then looks for next lowest number on each pass
exchange sort compares the smallest number to each of the rest of the numbers (but only changes this one?)
Explanation / Answer
Bubble Sort: Bubble sort is a sorting algorithm that operates by going through the list to be sorted repeatedly while comparing pairs of elements that are adjacent. If a pair of elements is in the wrong order they are swapped to place them in the correct order. This traversal is repeated until no further swaps are required (which means that the list is sorted). Since the smaller elements in the list come to the top as a bubble comes to the surface, it is given the name bubble sort. Bubble sort is a very simple sorting algorithm but it has an average case time complexity of O(n2) when sorting a list with n elements
Bubble Sorting algorithm With example:
public static void bubbleSort (int[] data)
{
for (int i = data.length - 1; i >= 0; i--)
{
// bubble up
for (int j = 0; j <= i - 1; j++)
{
if (data[j] > data[j + 1])
swap(data, j, j + 1);
}
}
}
The following tracks the code on an array with elements {38, 27, 43, 3, 9, 82, 10} for three rounds of bubbling.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
{38, 27, 43, 3, 9, 82, 10}
i: 6
{27, 38, 43, 3, 9, 82, 10}, j: 0
{27, 38, 43, 3, 9, 82, 10}, j: 1
{27, 38, 3, 43, 9, 82, 10}, j: 2
{27, 38, 3, 9, 43, 82, 10}, j: 3
{27, 38, 3, 9, 43, 82, 10}, j: 4
{27, 38, 3, 9, 43, 10, 82}, j: 5
i: 5
{27, 38, 3, 9, 43, 10, 82}, j: 0
{27, 3, 38, 9, 43, 10, 82}, j: 1
{27, 3, 9, 38, 43, 10, 82}, j: 2
{27, 3, 9, 38, 43, 10, 82}, j: 3
{27, 3, 9, 38, 10, 43, 82}, j: 4
i: 4
{3, 27, 9, 38, 10, 43, 82}, j: 0
{3, 9, 27, 38, 10, 43, 82}, j: 1
{3, 9, 27, 38, 10, 43, 82}, j: 2
{3, 9, 27, 10, 38, 43, 82}, j: 3
Exchange Sort:
Exchange sorts attempt to improve the ordering by comparing elements in pairs and interchanging them if they are not in sorted order. This operation is repeated until the table is sorted. Algorithms differ in how they systematically choose the two elements to be compared. The method for Exchange sort as follows
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
if (a[j] > a[j+1])
{
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
For i=o
9 2 5 4 7 8 compare 1st & 2nd ->
2 9 5 4 7 8 compare 2nd & 3rd ->
2 5 9 4 7 8 compare 3rd & 4th ->
2 5 4 9 7 8 compare 4th & 5th ->
2 5 4 7 9 8 compare 5th & 6th ->
2 5 4 7 8 9
i = 1 2 4 5 7 8 9
i = 2 2 4 5 7 8 9 on this pass no exchanges made
i = 3 2 4 5 7 8 9
i = 4 2 4 5 7 8 9
public static void bubbleSort (int[] data)
{
for (int i = data.length - 1; i >= 0; i--)
{
// bubble up
for (int j = 0; j <= i - 1; j++)
{
if (data[j] > data[j + 1])
swap(data, j, j + 1);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.