'삽입정렬'과 '버블정렬'의 차이

macros의 이미지

삽입과 버블의 차이가 느낌으로 안오네요... -_-
쉽게 설명 부탁드릴께요..

caplove의 이미지

삽입 정렬과 버블 정렬은 비슷한 정렬(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) 위치의 숫자를 반복해서 정렬하지요.
삽입 정렬은 각 반복 때마다 가장 작은 값을 찾아서 앞으로 넣어줍니다.
버블 정렬은 각 반복 때마다 가장 큰 값을 맨 뒤로 넣어줍니다.

하지만 두 정렬 모두 전체 정렬을 위해서 읽어야 되는 반복 작업의 개수는 동일합니다. [<- 이 내용은 두 알고리즘을 수행하기 위해서 걸리는 시간을 의미합니다. ^^]

lacovnk의 이미지

위에 분이 너무나도 설명 잘해주셨네요! :)

참고로, 버블이나 삽입 모두 거꾸로 구현하면, "가장 작은 녀석 먼저" 또는 "가장 큰 녀석 먼저" 제자리로 간다... 라고 분류를 할 수가 없게 되겠죠 :) 이런 결과만 기억하시면 안됩니다 ㅎㅎ

삽입 정렬은 제일 작은 녀석을 바꿔야 하니, 그 위치를 기억해놓고 있어야 하지만, 버블 정렬은 계속 바꾸면서 뒤로 갖고 가는 겁니다.

섞여 줄 서 있는 애들을 정렬한다고 칩시다.

버블정렬 : 일단 제일 앞 녀석 데리고 뒤로 가는 겁니다. 차례로 비교해나가다가, 더 큰 녀석이 있으면 더 큰 녀석을 뒤로 데리고 갑니다.... 그러면 제일 뒤에는 제일 큰 녀석이 서겠죠. 이런 식으로 계속 하면 정렬이 됩니다.

삽입정렬 : 처음부터 끝까지 봐서, 제일 작은 녀석을 제일 앞 자리와 바꿉니다. 두번째로 볼 때는 나머지에서 가장 작은 사람과 두 번째 녀석이랑 바꾸고..

반복 작업의 개수는 똑같지만, 이런 차이 때문에 조금 성능이 다를 수 있습니다. 읽기는 무척 빠르고, 쓰기는 무척 느리다고 하면, 삽입정렬이 훨씬 나은 성능을 보여주겠죠~ 그래봤자 O(n^2)이지만; 그래도;

http://home.lacovnk.net/

익명사용자의 이미지

혹시 삽입정렬이 아니라 선택정렬을 설명하고 있는 것이 아닙니까?

proneer의 이미지

처음 설명하신 분께서 설명하신 삽입정렬에 대한 내용은 선택정렬에 대한 내용입니다. 선택정렬은 버블정렬과 큰 차이를 보이기 때문에 크게 혼동되지 않습니다. 버블정렬에 대해서는 잘 설명해 주셨네요. 하지만 버블정렬 또한 거꾸로 구현하게 되면 작은 값부터 채워지게 구현될 수 있습니다.

삽입정렬은 다음과 같습니다.

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 이상 정렬완료~~

익명 사용자의 이미지

좋은 설명이네요. 감사 ^^

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.