C++

Forum

 
What is the name of this sorting algorithm ?

Flaze07 (231)
1
2
3
4
5
6
7
 
for (int i = 0; i < arr.size() - 1; ++i)
{
    if (arr.at(i) > arr.at(i + 1)) 
    {
        std::swap(arr.at(i), arr.at(i + 1));
    }
}


For quite some time I thought this was bubble sort then I found a bubble sort algorithm and it is not in any sense similiar to this
Last edited on
coder777 (8443)
It is not a sorting algorithm since it does not sort at all. It moves just a single element of the array.
Flaze07 (231)
Huh ?
But it sorts the array
Peter87 (11226)
It only works for some nearly sorted sequences. The loop will move an element at most one step to the left so if an element needs to be moved two or more steps to the left it won't get sorted.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int main()
{
	std::vector<int> arr = {1, 3, 5, 7, 2};
	
	for (int i = 0; i < arr.size() - 1; ++i)
	{
		if (arr.at(i) > arr.at(i + 1)) 
		{
			std::swap(arr.at(i), arr.at(i + 1));
		}
	}
	
	for (int i : arr)
	{
		std::cout << i << '\n';
	}
}
 
output
1
3
5
2 <-- out of order
7


The loop is admittedly similar to the inner workings of bubble sort. You don't need to add much code in order to turn it into a working bubble sort implementation.

1
2
3
4
5
6
7
8
9
10
11
12
13
 
bool swapped;
do
{
	swapped = false;
	for (int i = 0; i < arr.size() - 1; ++i)
	{
		if (arr.at(i) > arr.at(i + 1)) 
		{
			std::swap(arr.at(i), arr.at(i + 1));
			swapped = true;
		}
	}
} while (swapped);
Last edited on
Flaze07 (231)
I see... thank you :D
Wait...what if I have 2 loops one from first to end, one from end to first it will be a perfect sort algorithm right ?
Last edited on
Peter87 (11226)
No, that won't work.
jonnin (11429)
the perfect sort is bucket, which only works on integers really, though you can force it to work on a variety of data. It only looks at each item once, and does not move anything, O(N) and nearly instant up to very, very large lists. Once that becomes impractical due to data not being suitable for it, NlgN is about the best you can do, though that can be tweaked in a number of cool ways.

That aside, take an array, a small one with say 5 items, and try your algorithm on it. If that works, try it on 10, and make sure to try sorting items that are way off like 5,1,3,4,2 or 10,9,8,7,6,5,4,3,2,1. This should show you why your proposed algorithm (if I understood it) does not work correctly for all arrays, only for certain ones.

Topic archived. No new replies allowed.