Sort 알고리즘(버블정렬)

버블정렬(Bubble Sort) 이란 인접한 레코드의 키값을 비교하여 순서화 되어 있지 않으면 교환 하는것
오름차순 정렬의 경우 첫번째 키와 두 번째 키를 비교하여 두번째 자료가 첫번째 자료보다 작으면 이를 맞 교환, 결국 이를 반복하면 리스트의 마지막엔 가장 큰 키를 갖는 데이터가 들어 있게 된다.
평균 연산 시간은 O(n2)


import java.util.Random;
class BubbleSort {
//버블정렬1(좌측부터)
int[] sort1(int a[])  {
      int  temp, num = a.length;;  
  boolean flag=true;
      while(flag) {
                flag = false;
//i를 미리 증가, 처음것 다음부터 비교
                for(int i=0; i < num-1; ++i) {  
                      if(a[i] > a[i+1]) {    // ascending sort
                          temp = a[i]; a[i] = a[i+1];
                          a[i+1] = temp;  
  flag = true;
                      } 
                }   
        }  
return a;
}  

//버블정렬2(우측부터)
int[] sort2(int[] a) {
int temp, num = a.length;
boolean flag = true; //자료 위치 교환의 발생 여부
//자료의 위치 교환이 발생하는 동안 반복한다.
while(flag) {
// 마지막 포인터를 줄이면서 마지막 포인터까지
//비교하면서 우측이 작으면 자리를 바꿈...
num--;
flag = false;
for(int i=0; i<num; i++) {
if (a[i] > a[i+1]){
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
flag = true;
}
}
}
return a;
}
public static void main(String[] args){
int nansu[] = new int[10000];
int[] sortedArray = new int[10000];
int[] halfSortedArray = new int[10000];
int[] reverseArray = new int[10000];
int[] temp = new int[10000];
long startTime, elapsedTime, counter;

BubbleSort mySort = new BubbleSort();  
//----------------- 난수 발생시킴
Random r = new Random();
for(int i=0; i<10000; i++) {
nansu[i] = r.nextInt(10000);
}
//-----------------------------------

//------------------------------------------------------------------------------
//우선 난수를 정렬하고, 정렬된 상태(최선의상황)을 다시 정렬시킴
//------------------------------------------------------------------------------
counter=0;
sortedArray = mySort.sort2(nansu);
startTime = System.currentTimeMillis();
do {
counter++;
temp = mySort.sort2(sortedArray);
  } while (System.currentTimeMillis() - startTime < 1000);
elapsedTime = (System.currentTimeMillis()- startTime) / counter;
System.out.println("[최선의 상황 수행시간] " + elapsedTime + "ms");
//-------------------------------------------------------------------------------

//-------------------------------------------------------------------------------
//반쯤 정열후 ...
//-------------------------------------------------------------------------------
counter=0;
halfSortedArray = sortedArray;
for(int i=0; i<5000; i++) {
halfSortedArray[i] = r.nextInt()*10000;
}
startTime = System.currentTimeMillis();
do {
counter++;
temp = mySort.sort2(halfSortedArray);
  } while (System.currentTimeMillis() - startTime < 1000);
elapsedTime = (System.currentTimeMillis()- startTime) / counter;
System.out.println("[반쯤 정렬 수행시간] " + elapsedTime + "ms");
//-------------------------------------------------------------------------------

//-------------------------------------------------------------------------------
//역순상태
//-------------------------------------------------------------------------------
counter=0;
for(int i=0;i<sortedArray.length;i++) {
reverseArray[sortedArray.length-i-1] = sortedArray[i];
}
startTime = System.currentTimeMillis();
do {
counter++;
temp = mySort.sort2(reverseArray);
  } while (System.currentTimeMillis() - startTime < 1000);
elapsedTime = (System.currentTimeMillis()- startTime) / counter;
System.out.println("[역순 상태 수행시간] " + elapsedTime + "ms");
//--------------------------------------------------------------------------------
}
}