삽입 정렬과 버블 정렬은 비슷한 정렬(sorting) 기법입니다. 두 방법의 차이는 간단히 첫번째 반복(iteration)에서 가장 작은 값(또는 가장 큰 값)을 선택하는 방법의 차이입니다.
예를 들어서 설명드리면(가장 작은 값부터 가장 큰 값으로 정렬한다고 가정합시다.), 삽입 정렬에서는 첫번째 반복에서 가장 작은 값을 골라서 첫번째값으로 설정하는 방식입니다. (말이 더 어렵지요. ^^)
2 8 1 5 3 9 <- 1부터 9까지 한번 죽 스캔하면서 가장 작은 값을 찾습니다. '1'이지요. 이 값을 첫번째 값인 '2'와 바꿔 넣습니다.
1 8 2 5 3 9 <- 두번째 반복에서는 두번째 값인 8부터 끝 9까지 한번 죽 스캔하면서 가장 작은 값을 찾습니다. 그러면 '2'가 가장 작은 값이지요. 이 값을 두번째 반복의 첫번재 값인 '8'과 바꿔 넣습니다.
1 2 8 5 3 9 <- 세번째 반복에서는 세번재 값인 8부터 끝 9까지 같은 방법으로 가장 작은 값을 찾아서 세번째 반복의 첫번째 값과 바꿔 넣습니다.
이와 같은 방법으로 처음부터 끝가지 다 돌면 정렬이 완성됩니다. (각각의 반복때마다 전체를 [물론 1개식 덜 읽지만] 다 읽어야 하고 이 반복을 앞에서부터 끝가지 해야 합니다.)
반면 버블정렬은 첫번째 정렬에서 가장 큰 값을 가장 뒤로 보내는 방법입니다. (역시나 말이 더 어렵지요. ^^)
2 8 1 5 3 9 <- 첫번째 반복(iteration)에서는 첫번째 값 2부터 끝 값 9까지 두개씩 비교하면서 앞의 값이 뒤의 값보다 더 크면 서로 교환하는 방법입니다.
2와 8에서는 2가 더 작으므로 넘어가고, 8과 1은 8이 더 크므로 교환, (2 1 8 5 3 9) 다음 8과 5는 8이 더 크므로 교환, (2 1 5 8 3 9) 8과 3은 8이 더 크므로 교환, (2 1 5 3 8 9) 다음 8과 9는 8이 더 작으므로 넘어갑니다. 이렇게 첫번째 반복이 끝납니다.
2 1 5 8 3 9 <- 두번째 반복에서는 첫번째 값 2부터 끝 값 1개전 3까지 같은 방법으로 두개씩 비교하면서 앞의 값이 뒤의 값보다 더 크면 서로 교환합니다.
2와 1에서는 2가 더 크므로 교환, (1 2 5 8 3 9) 다음 2와 5는 2가 더 작으므로 넘어가고, 5와 8 넘어가고, 8과 3은 교환, (1 2 5 3 8 9) 두번째 반복 종료
1 2 5 3 8 9 <- 세번째 반복에서는 첫번째 값 1부터 끝 값 2개전 3까지 같은 방법으로 정렬합니다.
네번재 반복에서는 첫번째 값부터 끝 값 3개전, ... 이렇게 반복하지요.
어때요? 버블 정렬의 직관적 의미를 혹시 느끼셨읍니까? ^^ 각 반복에서 처음부터 마지막까지 2개씩 교환하면서 큰 값을 뒤쪽으로 밀어나갑니다. 즉 첫번째 반복에서는 가장 큰 값이 가장 맨 뒤에 오게 됩니다. (처음부터 2개씩 앞의 값이 뒤의 값보다 크면 2개씩 바꾸어 나가므로 결국 가장 큰 값이 맨 뒤에 오게 되죠. ^^) 따라서 두번째 반복에서는 처음부터 맨 뒤 (가장 큰 값) 하나 전까지만 반복합니다. 그러면 맨 뒤 하나 전에는 두번째로 큰 값이 오게 되지요.
전체 반복의 관점에서 보면 삽입 정렬은 (1, n), (2, n), (3, n) ... ... (n-1, n) 위치의 숫자들을 반복해서 정렬합니다.
버블 정렬은 (1, n), (1, n-1), (1, n-2) ... ... (1, 2) 위치의 숫자를 반복해서 정렬하지요.
삽입 정렬은 각 반복 때마다 가장 작은 값을 찾아서 앞으로 넣어줍니다.
버블 정렬은 각 반복 때마다 가장 큰 값을 맨 뒤로 넣어줍니다.
하지만 두 정렬 모두 전체 정렬을 위해서 읽어야 되는 반복 작업의 개수는 동일합니다. [<- 이 내용은 두 알고리즘을 수행하기 위해서 걸리는 시간을 의미합니다. ^^]
처음 설명하신 분께서 설명하신 삽입정렬에 대한 내용은 선택정렬에 대한 내용입니다. 선택정렬은 버블정렬과 큰 차이를 보이기 때문에 크게 혼동되지 않습니다. 버블정렬에 대해서는 잘 설명해 주셨네요. 하지만 버블정렬 또한 거꾸로 구현하게 되면 작은 값부터 채워지게 구현될 수 있습니다.
삽입정렬은 다음과 같습니다.
5 3 8 1 2 7 이라는 값이 있다고 하면 처음 값은 정렬되어 있다고 판단하고, 두번째 부터 비교합니다.
3을 선택하여 5와 비교해서 작으므로 5는 뒤로 밀려나고 앞에 3이 삽입됩니다.
3 5 8 1 2 7 다음 8을 선택하여 앞에서 부터 비교합니다. 8보다 큰값이 없으므로 그대로 둡니다.
3 5 8 1 2 7 다음 1을 선택하여 앞에서 부터 비교하면 3보다 작기 때문에 3부터 8까지의 값이 뒤로 밀려나고 1이 맨 앞에 삽입됩니다.
1 3 5 8 2 7 다음 2가 선택되고 마찬가지고 1보다 크고 3보다 작으므로 3부터 8까지 값을 뒤로 미뤄내고 3앞에 삽입됩니다.
삽입 정렬과 버블
삽입 정렬과 버블 정렬은 비슷한 정렬(sorting) 기법입니다. 두 방법의 차이는 간단히 첫번째 반복(iteration)에서 가장 작은 값(또는 가장 큰 값)을 선택하는 방법의 차이입니다.
예를 들어서 설명드리면(가장 작은 값부터 가장 큰 값으로 정렬한다고 가정합시다.), 삽입 정렬에서는 첫번째 반복에서 가장 작은 값을 골라서 첫번째값으로 설정하는 방식입니다. (말이 더 어렵지요. ^^)
2 8 1 5 3 9 <- 1부터 9까지 한번 죽 스캔하면서 가장 작은 값을 찾습니다. '1'이지요. 이 값을 첫번째 값인 '2'와 바꿔 넣습니다.
1 8 2 5 3 9 <- 두번째 반복에서는 두번째 값인 8부터 끝 9까지 한번 죽 스캔하면서 가장 작은 값을 찾습니다. 그러면 '2'가 가장 작은 값이지요. 이 값을 두번째 반복의 첫번재 값인 '8'과 바꿔 넣습니다.
1 2 8 5 3 9 <- 세번째 반복에서는 세번재 값인 8부터 끝 9까지 같은 방법으로 가장 작은 값을 찾아서 세번째 반복의 첫번째 값과 바꿔 넣습니다.
이와 같은 방법으로 처음부터 끝가지 다 돌면 정렬이 완성됩니다. (각각의 반복때마다 전체를 [물론 1개식 덜 읽지만] 다 읽어야 하고 이 반복을 앞에서부터 끝가지 해야 합니다.)
반면 버블정렬은 첫번째 정렬에서 가장 큰 값을 가장 뒤로 보내는 방법입니다. (역시나 말이 더 어렵지요. ^^)
2 8 1 5 3 9 <- 첫번째 반복(iteration)에서는 첫번째 값 2부터 끝 값 9까지 두개씩 비교하면서 앞의 값이 뒤의 값보다 더 크면 서로 교환하는 방법입니다.
2와 8에서는 2가 더 작으므로 넘어가고, 8과 1은 8이 더 크므로 교환, (2 1 8 5 3 9) 다음 8과 5는 8이 더 크므로 교환, (2 1 5 8 3 9) 8과 3은 8이 더 크므로 교환, (2 1 5 3 8 9) 다음 8과 9는 8이 더 작으므로 넘어갑니다. 이렇게 첫번째 반복이 끝납니다.
2 1 5 8 3 9 <- 두번째 반복에서는 첫번째 값 2부터 끝 값 1개전 3까지 같은 방법으로 두개씩 비교하면서 앞의 값이 뒤의 값보다 더 크면 서로 교환합니다.
2와 1에서는 2가 더 크므로 교환, (1 2 5 8 3 9) 다음 2와 5는 2가 더 작으므로 넘어가고, 5와 8 넘어가고, 8과 3은 교환, (1 2 5 3 8 9) 두번째 반복 종료
1 2 5 3 8 9 <- 세번째 반복에서는 첫번째 값 1부터 끝 값 2개전 3까지 같은 방법으로 정렬합니다.
네번재 반복에서는 첫번째 값부터 끝 값 3개전, ... 이렇게 반복하지요.
어때요? 버블 정렬의 직관적 의미를 혹시 느끼셨읍니까? ^^ 각 반복에서 처음부터 마지막까지 2개씩 교환하면서 큰 값을 뒤쪽으로 밀어나갑니다. 즉 첫번째 반복에서는 가장 큰 값이 가장 맨 뒤에 오게 됩니다. (처음부터 2개씩 앞의 값이 뒤의 값보다 크면 2개씩 바꾸어 나가므로 결국 가장 큰 값이 맨 뒤에 오게 되죠. ^^) 따라서 두번째 반복에서는 처음부터 맨 뒤 (가장 큰 값) 하나 전까지만 반복합니다. 그러면 맨 뒤 하나 전에는 두번째로 큰 값이 오게 되지요.
전체 반복의 관점에서 보면 삽입 정렬은 (1, n), (2, n), (3, n) ... ... (n-1, n) 위치의 숫자들을 반복해서 정렬합니다.
버블 정렬은 (1, n), (1, n-1), (1, n-2) ... ... (1, 2) 위치의 숫자를 반복해서 정렬하지요.
삽입 정렬은 각 반복 때마다 가장 작은 값을 찾아서 앞으로 넣어줍니다.
버블 정렬은 각 반복 때마다 가장 큰 값을 맨 뒤로 넣어줍니다.
하지만 두 정렬 모두 전체 정렬을 위해서 읽어야 되는 반복 작업의 개수는 동일합니다. [<- 이 내용은 두 알고리즘을 수행하기 위해서 걸리는 시간을 의미합니다. ^^]
위에 분이 너무나도
위에 분이 너무나도 설명 잘해주셨네요! :)
참고로, 버블이나 삽입 모두 거꾸로 구현하면, "가장 작은 녀석 먼저" 또는 "가장 큰 녀석 먼저" 제자리로 간다... 라고 분류를 할 수가 없게 되겠죠 :) 이런 결과만 기억하시면 안됩니다 ㅎㅎ
삽입 정렬은 제일 작은 녀석을 바꿔야 하니, 그 위치를 기억해놓고 있어야 하지만, 버블 정렬은 계속 바꾸면서 뒤로 갖고 가는 겁니다.
섞여 줄 서 있는 애들을 정렬한다고 칩시다.
버블정렬 : 일단 제일 앞 녀석 데리고 뒤로 가는 겁니다. 차례로 비교해나가다가, 더 큰 녀석이 있으면 더 큰 녀석을 뒤로 데리고 갑니다.... 그러면 제일 뒤에는 제일 큰 녀석이 서겠죠. 이런 식으로 계속 하면 정렬이 됩니다.
삽입정렬 : 처음부터 끝까지 봐서, 제일 작은 녀석을 제일 앞 자리와 바꿉니다. 두번째로 볼 때는 나머지에서 가장 작은 사람과 두 번째 녀석이랑 바꾸고..
반복 작업의 개수는 똑같지만, 이런 차이 때문에 조금 성능이 다를 수 있습니다. 읽기는 무척 빠르고, 쓰기는 무척 느리다고 하면, 삽입정렬이 훨씬 나은 성능을 보여주겠죠~ 그래봤자 O(n^2)이지만; 그래도;
http://home.lacovnk.net/
삽입정렬, 선택정렬???
혹시 삽입정렬이 아니라 선택정렬을 설명하고 있는 것이 아닙니까?
선택정렬에 대한 설명이군요...
처음 설명하신 분께서 설명하신 삽입정렬에 대한 내용은 선택정렬에 대한 내용입니다. 선택정렬은 버블정렬과 큰 차이를 보이기 때문에 크게 혼동되지 않습니다. 버블정렬에 대해서는 잘 설명해 주셨네요. 하지만 버블정렬 또한 거꾸로 구현하게 되면 작은 값부터 채워지게 구현될 수 있습니다.
삽입정렬은 다음과 같습니다.
5 3 8 1 2 7 이라는 값이 있다고 하면 처음 값은 정렬되어 있다고 판단하고, 두번째 부터 비교합니다.
3을 선택하여 5와 비교해서 작으므로 5는 뒤로 밀려나고 앞에 3이 삽입됩니다.
3 5 8 1 2 7 다음 8을 선택하여 앞에서 부터 비교합니다. 8보다 큰값이 없으므로 그대로 둡니다.
3 5 8 1 2 7 다음 1을 선택하여 앞에서 부터 비교하면 3보다 작기 때문에 3부터 8까지의 값이 뒤로 밀려나고 1이 맨 앞에 삽입됩니다.
1 3 5 8 2 7 다음 2가 선택되고 마찬가지고 1보다 크고 3보다 작으므로 3부터 8까지 값을 뒤로 미뤄내고 3앞에 삽입됩니다.
1 2 3 5 8 7 마지막으로 7이 선택되어 8앞에 삽입됩니다.
1 2 3 5 7 8 이상 정렬완료~~
good
좋은 설명이네요. 감사 ^^
댓글 달기