<div class="warning"> 여기서 사용된 차트를 제외한 그림및 플래쉬 자료에 대한 저작권은 전북대학교 박순철 교수님께 있습니다. </div>

설명#

Bubble Sort 예제

<object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://active.macromedia.com/flash4/cabs/swflash.cab#version=4,0,0,0" width="500" height="250"> <param name="movie" value="http://internet512.chonbuk.ac.kr/datastructure/sort/flash/bubble(new).swf"> <param name="play" value="false"> <param name="loop" value="false"> <param name="quality" value="high"> <embed src="http://internet512.chonbuk.ac.kr/datastructure/sort/flash/bubble(new).swf" play="false" loop="false" quality="high" pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" width="529" height="414"></embed> </object>

Bubble Sort 예제

<object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://active.macromedia.com/flash4/cabs/swflash.cab#version=4,0,0,0" width="500" height="250"> <param name="movie" value="http://internet512.chonbuk.ac.kr/datastructure/sort/flash/bubble_sort.swf"> <param name="play" value="false"> <param name="loop" value="false"> <param name="quality" value="high"> <embed src="http://internet512.chonbuk.ac.kr/datastructure/sort/flash/bubble_sort.swf" play="false" loop="false" quality="high" pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" width="520" height="420"></embed> </object>

The bubble sort is the oldest and simplest sort in use. Unfortunately, it's also the slowest.

The bubble sort works by comparing each item in the list with the item next to it, and swapping them if required. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items (in other words, all items are in the correct order). This causes larger values to "bubble" to the end of the list while smaller values "sink" towards the beginning of the list.

The bubble sort is generally considered to be the most inefficient sorting algorithm in common usage. Under best-case conditions (the list is already sorted), the bubble sort can approach a constant O(n) level of complexity. General-case is an abysmal O(n<span class="sup">2</span>).

While the insertion, selection, and shell sorts also have O(n<span class="sup">2</span>) complexities, they are significantly more efficient than the bubble sort.

A fair number of algorithm purists (which means they've probably never written software for a living) claim that the bubble sort should never be used for any reason. Realistically, there isn't a noticeable performance difference between the various sorts for 100 items or less, and the simplicity of the bubble sort makes it attractive. The bubble sort shouldn't be used for repetitive sorts or sorts of more than a couple hundred items.

  • 장점: Simplicity and ease of implementation.
  • 단점: Horribly inefficient.

실행횟수

O(n<span class="sup">2</span>)

자바 소스#

public class BubbleSort {

  public static void sort(int numbers[]) {
    int i, j, temp;
    int array_size = numbers.length;

    for (i = (array_size - 1); i >= 0; i--) {
      for (j = 1; j <= i; j++) {
        if (numbers[j - 1> numbers[j]) {
          temp = numbers[j - 1];
          numbers[j - 1= numbers[j];
          numbers[j= temp;
        }
      }
    }
  }

  public static void main(String[] args) {
    int[] a = 4731582};
    sort(a);
    for (int i = 0; i < a.length; i++)
      System.out.print(a[i]+"  ");
  }
}

효율성#

bubble.jpg

Add new attachment

Only authorized users are allowed to upload new attachments.

List of attachments

Kind Attachment Name Size Version Date Modified Author Change note
jpg
bubble.jpg 31.8 kB 1 14-Jul-2007 21:28 DongGukLee
« This page (revision-3) was last changed on 16-Jul-2007 21:30 by DongGukLee