버블 정렬
개념
버블 정렬을 실행했을 때 나오는 그림.
눈으로 보는 버블 정렬
1번째와 2번째 원소를 비교하여 정렬하고, 2번째와 3번째, ..., n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 이번에는 n-2번째와 n-1번째까지, ...해서 최대 n(n-1)/2 번 정렬한다. 한 번 돌 때마다 마지막 하나가 정렬되므로 원소들이 거품이 올라오는 것처럼 보여 거품정렬이다.
거의 모든 상황에서 최악의 성능을 보여준다. 단, 이미 정렬된 자료에서는 1번만 돌면 되기 때문에 최선의 성능을 보여준다. 이미 정렬된 자료를 정렬하는 바보짓을 왜 하냐는 의문이 들 수 있지만, 정렬 알고리즘은 자료가 정렬되어 있는지 아닌지는 모르고 작동하기 때문에 의미가 있다.
가장 손쉽게 구현하여 사용할 수 있지만, 만들기가 쉽고 직관적일 뿐이지 알고리즘적 관점에서 보면 대단히 비효율적인 정렬 방식이다.
상세 보기
인접한 두 원소를 비교 하여 정렬하는 방법입니다.
단순히 A > B 라는 조건식을 이용하여 1회전 마다 큰 값이든 작은 값이든 하나씩 위치를 맞춰가는 방식으로
정렬하고자 하는 자료의 n의 2승만큼 반복하여 정렬합니다.
- 오름 차순 : 작은 값을 먼저 오게 만드는 정렬 방식 ( 1, 2, 3 ... )으로 A>B 라면 교환하여 정렬합니다.
- 내림 차순 : 큰 값을 먼저 오게 만드는 정렬 방식 ( ... 3, 2, 1 ) 으로 A<B 라면 교환하여 정렬합니다.
코드
내림차순
using System;
namespace ConsoleApp1
{
class Program
{
static void Main(string[] args)
{
int[] nArr = new int[]{ 1, 4, 3, 5, 9, 6, 2, 7, 8, 10 };
int nTemp;
int nCount = 0;
for(int i = 0; i < nArr.Length-1; i++)
{
for (int j = 0; j < nArr.Length-1; j++)
{
if(nArr[j] < nArr[j+1])
{
nTemp = nArr[j+1];
nArr[j+1] = nArr[j];
nArr[j] = nTemp;
}
nCount++;
}
}
Console.WriteLine("Count : {0}", nCount);
for(int i = 0; i < nArr.Length; i++)
Console.Write(nArr[i] + "\t");
}
}
}조건식만 바꿔준다면 오름차순으로 정렬됩니다. ( nArr[j] > nArr[j+1] )
결과에서 알수있듯 총 비교횟수는 81회입니다. 이는 데이터 총갯수 - 1의 2승 만큼 계산되어 진것으로 연산순서는
아래와 같습니다.
장단점
장점
- 구현이 간단하다
단점
- 구조상 모든 요소들을 비교하고 이동시키기 때문에 효율적이지 못하다
일반적으로 자료의 이동 보다 교환 작업이 연산 작업이 복잡하기 때문에 구현의 단순성에도 불구하고
거의 쓰이지 않습니다.
정렬 알고리즘 테스트
종류|최소|최대|정렬시간 (10만개 테스트)
---|---|---|---
퀵 정렬|n log n|n^2|32 ms
삽입 정렬|n|n^2|8142 ms
선택 정렬|n^2|n^2|13499 ms
버블 정렬|n^2|n^2|53488 ms
파생형
칵테일 정렬
셰이커 정렬(shaker sort)라고도 한다. 홀수 번째 돌 때는 앞부터, 짝수 번째는 뒤부터 훑는 정렬. 당연하겠지만 이 쪽은 마지막과 처음이 번갈아가며 정렬된다. 제일 처음에 하나, 제일 뒤에 하나, 다시 제일 앞에 하나, 또 제일 뒤에 하나를 정렬하면서 마치 정렬하는 과정이 앞뒤로 마구 흔드는게 칵테일을 마구 흔들어 섞는것과 비슷해보인다 하여 칵테일(혹은 이름을 합쳐서 칵테일 셰이커) 정렬이라는 이름이 붙었다.
- 콤브 정렬(comb sort)
기본 형태는 버블정렬과 같지만 예를 들어 처음에 a[0]에서 10칸 띄워서 a[11]과 비교해서 치환하는 식으로 대상을 띄웠다가 한 바퀴 돌면 띄우는 간격을 좁혀서 정렬하는 방식이다. 이렇게 하면 버블정렬과 다를 게 없어졌을 시점엔 정렬이 거의 끝나 있는데, 이 단계까지 가는 동안 모양이 마치 닭의 볏을 닮았다 하여 콤브정렬이라는 이름이 붙었다. 이렇게 본다면 콤브정렬이 버블정렬보다 좋아 보이지만 단점이 있는데 버블정렬이 stable sort이지만 콤브정렬은 그렇지 못하다.
