Life Of D22

Selection sort & Heap sort & Quick sort  정렬 속도 비교

학교 과제로 나온 ... 시간 복잡도를 비교하는 과제 ...

음 ... quick 정렬이 나름 제일 빠른 줄 알았지만 ( nlogn 이라고 하지만 ... ) 이런 속도 차이가 ...

selection, insert, bubble 등 이런 정렬들은 ... 일정 자릿수 이상의 값을 입력 하였을 시에 ...

미칠듯한 정렬 시간이 나왔다.

첨부 된 그림은 실제로 적용 해 본 후 나온 결과 화면 ...


※ 정렬 되지 않은 자료일 경우 정렬하는데 얼마 걸리지 않는데, 정렬 된 자료 일 경우 ... 생각보다 시간이 걸렸다. 여러 책에 따르면 Quick sort는 정렬된 자료일 경우 정렬하는데 걸리는 시간이 더 걸린다고 하는데 ... 으흠 ... 쏘스에 따라 달라짐은 이를 어떡하랴 ?

화면을 클릭하면 크게 보일까? 흠흠 ...

( 테스트한 자료는 ... 50,000 에서부터 시작하여 2,000,000 까지의 데이터를 무작위로 생성하여 테스트 하였다. JAVA로 작업 하였음 )


- PS -
 이론상 Quick sort의 경우 정렬된 경우는 위의 결과처럼 나오지 않는다. 즉 복잡도가 증가해서 Selection sort의 경우처럼 느린 경우를 볼 수 있다.
 즉 작성하는 소스에 따라서 결과값은 달리 나온다.

/*
SelectionSort : sort contiguous list by the selection sort method.
Pre : The contiguous list list has been created. Each entry of list contains a key.
Post : The entries of list have been rearranged so that the keys in all the entries are sorted into nondecreasing order.
Uses : MaxKey, Swap
*/

void SelectionSort( List * list ){
   Position current; /* position of place being correctly filled */
   Position max; /* position of largest remaining key */
   for ( current = list -> count - 1; current > 0; current-- ){
      max = MaxKey ( 0, current, list );
      Swap ( max, current, list );
   }
}

/*
MaxKey : find the position of the largest key in the sublist.
Pre : The contiguous list list has been created. low and high are valid positions in list.
Post : The position of the entry between low and high with the largest key is returned
*/
Position MaxKey( Position low, Position high, List * list ){
   Position largest; /* position of largest key so far */
   Position current; /* index for the contigous list */
   largest = low;
   for( current = low + 1; current <= high; current++ )
      if( LT( list->entry[ largest ].key, list->entry[ current ].key ) )
         largest = current; 

   return largest;
}

/*
Swap : swap two entries in the contiguos list.
Pre : The contiguos list list has been created. low and high are valied positions in list.
Post : The entry at position low is swapped with the entry at position high
*/
void Swap( Position low, Position high, List * list ){
   ListEntry temp = list->entry[ low ];
   list->entry[ low ] = list->entry[ high ];
   list->entry[ high ] = temp;
}


/* 발췌 ---------------- Data Structures And Program Design in C */

public class Test {
   public static void main(String [] args){
      int [] array = { 7, 2, 3, 1, 5, 6 };
      SelectionSort selectionSort = new SelectionSort(array);
      selectionSort.runSort();
      selectionSort.print();
   }
}

class SelectionSort{
 
   int [] array;
 
   public SelectionSort(int [] array){
      this.array = array;
   }
 
   public void runSort(){
      int current;
      int max;
      for( current = array.length-1; current > 0 ; current-- ){
         max = this.getMaxKey( 0, current , array);
         runSwap( max, current, array );
      }
   }
 
   public int print(){
      int length = this.array.length;
      for( int count = 0; count < length; count++ )
         System.out.println(array[count]);
      return length;
   }
 
   private int getMaxKey( int low, int high, int [] array ){
 
      int largest;
      int current;
      largest = low;
 
      for( current = low+1 ; current <= high; current++ ){
        if( array[ largest ] <= array[ current ] ){
           largest = current;
        }
     }
 
    return largest;
 }
 
   private void runSwap( int low, int high, int [] array ){
      int temp = array[ high ];
      array[ high ] = array[ low ];
      array[ low ] = temp;
   }
}