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

설명#

InsertionSort.jpg

Insertion 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/insertion(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/insertion(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>

Insertion 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/insertion_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/insertion_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 insertion sort works just like its name suggests - it inserts each item into its proper place in the final list. The simplest implementation of this requires two list structures - the source list and the list into which sorted items are inserted. To save memory, most implementations use an in-place sort that works by moving the current item past the already sorted items and repeatedly swapping it with the preceding item until it is in place.

Like the bubble sort, the insertion sort has a complexity of O(n<span class="sup">2</span>). Although it has the same complexity, the insertion sort is a little over twice as efficient as the bubble sort.

The insertion sort is a good middle-of-the-road choice for sorting lists of a few thousand items or less. The algorithm is significantly simpler than the shell sort, with only a small trade-off in efficiency. At the same time, the insertion sort is over twice as fast as the bubble sort and almost 40% faster than the selection sort. The insertion sort shouldn't be used for sorting lists larger than a couple thousand items or repetitive sorting of lists larger than a couple hundred items.

  • 장점: Relatively simple and easy to implement.
  • 단점: Inefficient for large lists.

실행횟수

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

자바 소스#

public class InsertionSort {

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

    for (i = 1; i < array_size; i++) {
      index = numbers[i];
      j = i;
      while ((j > 0&& (numbers[j - 1> index)) {
        numbers[j= numbers[j - 1];
        j = j - 1;
      }
      numbers[j= index;
    }
  }

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

효율성#

insertion.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
InsertionSort.jpg 84.2 kB 1 16-Jul-2007 21:21 DongGukLee
jpg
insertion.jpg 30.0 kB 1 14-Jul-2007 20:37 DongGukLee
« This page (revision-18) was last changed on 22-Aug-2007 10:19 by DongGukLee