자바정렬, 소트, Sort 알고리즘(버블정렬, bubble 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");
//--------------------------------------------------------------------------------
}
}
오름차순 정렬의 경우 첫번째 키와 두 번째 키를 비교하여 두번째 자료가 첫번째 자료보다 작으면 이를 맞 교환, 결국 이를 반복하면 리스트의 마지막엔 가장 큰 키를 갖는 데이터가 들어 있게 된다.
평균 연산 시간은 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");
//--------------------------------------------------------------------------------
}
}
[개강임박강좌, 오프라인교육장에 오시면 보다 자세히 배울 수 있습니다.]
오라클자바커뮤니티에서 운영하는 개발자 전문교육 ,개인80%환급(www.onjprogramming.co.kr)
[주간]
[11/13]SQL초보에서실전전문가까지
[11/13]안드로이드개발자과정
[11/18]Spring3.X, MyBatis, Hibernate실무과정
[11/18]iPhone 하이브리드 앱 개발 실무과정
[평일야간]
[11/08]C#,ASP.NET마스터
[11/08]Spring3.X, MyBatis, Hibernate실무과정
[11/12]iPhone 하이브리드 앱 개발 실무과정
[11/14]JAVA&WEB프레임워크실무과정
[주말]
[11/09]JAVA&WEB프레임워크실무과정
[11/09]웹퍼블리싱 마스터
[11/16]C#,ASP.NET마스터
[11/16]PL/SQL,오라클힌트,SQL튜닝,사례연구
[11/16]ASP.NET4.0 MVC 프로그래밍
[11/16]Spring3.X, MyBatis, Hibernate실무과정
오라클자바커뮤니티에서 운영하는 개발자 전문교육 ,개인80%환급(www.onjprogramming.co.kr)
[주간]
[11/13]SQL초보에서실전전문가까지
[11/13]안드로이드개발자과정
[11/18]Spring3.X, MyBatis, Hibernate실무과정
[11/18]iPhone 하이브리드 앱 개발 실무과정
[평일야간]
[11/08]C#,ASP.NET마스터
[11/08]Spring3.X, MyBatis, Hibernate실무과정
[11/12]iPhone 하이브리드 앱 개발 실무과정
[11/14]JAVA&WEB프레임워크실무과정
[주말]
[11/09]JAVA&WEB프레임워크실무과정
[11/09]웹퍼블리싱 마스터
[11/16]C#,ASP.NET마스터
[11/16]PL/SQL,오라클힌트,SQL튜닝,사례연구
[11/16]ASP.NET4.0 MVC 프로그래밍
[11/16]Spring3.X, MyBatis, Hibernate실무과정
댓글 없음:
댓글 쓰기