22. 10. 26 - [ 플러스 알파 ] 버블 정렬 , 셀렉션 정렬, 정렬 장단점

 

 

-- INDEX --

 

1. 버블정렬 ( bubble sort )	2. 선택 정렬 ( selection sort )	3. 정렬별 장단점과 시간복잡도
하나하나 비교 큰 수 뒤로 보내기	정렬 최소 값의 index 활용 비교하여 작은 값 - 맨 앞에 넣어주기	내용 체크

 

 

 

---

 

 

 

 

1. 버블 정렬 - bubble sort

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
• 정렬을 하는 방식이 물속에서 물 위로 올라오는 물방울 모양과 같다 하여 버블 정렬이라고 한다.
• 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
• 선택 정렬과 기본 개념이 유사하다.
• 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, …
• 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.

 

• 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 
• 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 
• 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 
• 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

 

• 버블 정렬은 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 끝부터 정렬하는 방식
• 코드가 간단하므로 구현이 간편
• n개의 원소에 대하여 n개의 메모리를 사용
• 데이터를 하나씩 비교할 수 있어서 정밀하게 비교가 가능하나 비교 횟수가 많아지므로 성능면에서는 좋은 방법이 아님
• 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소를 마지막 자리로 정렬하는 식으로 정렬된다.

 

 

---

 

1-1 : 버블 정렬(bubble sort) 알고리즘의 예제

 

 

---

 

 

6-2 : 버블 정렬 실습 

 

 

---

 

---

 

이렇게해도 정렬 완료

 

성능 좋게 해 주려면– 불필요한 비교 작업 없도록 해주기 ~

 

 

 

---

 

//버블정렬 ( 실제로 쓸 일 거의 없다 n^2 제곱만큼 걸림
public static int[] bubbleSort(int[] arr) {

    //숫자 맨 앞부터 2개씩 비교 ( i번째 요소, i+1번째 요소)
    //만약에, [ i번째요소 > i+1번째요소 ] 이라면 둘이 자리 바꿈

    //위 작업을 반복

    for (int n = 0; n < arr.length-1; n++) {

        //제일 큰 수 맨 뒤로 하나씩 보내기
        for (int i = 0; i < arr.length-1 -n; i++) {

            if(arr[i] > arr[i+1]) {
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1]=temp;
            }

        }

    }

    return arr;

}//method

 

 

 

 

---

 

 

 

 

2. 셀렉션 정렬

• 선택 정렬은 배열 내의 기준이 되는 수(A[0]) 와 나머지의 수를 비교하여
• 오름차순일 경우 낮은 수, 내림차순일 경우 높은 수를 앞으로 보내는 방식
• [ 오름차순기준 ]
• 첫 번째 for문에서 기준값 [0] 번째 Index의 값과 나머지 값을 비교하여 가장 낮은 수를 앞으로 보내줍니다.
• 그다음부터는 기준값을 [0] 번째 Index에서 [1] 번째 Index값으로 바꿔준 뒤 [0] 번째에 있는 수를 제외한 나머지 숫자와 다시 비교
• 이 작업을 정렬이 완료될 때까지 반복하는 것이 선택 정렬

 

 

---

 

 

 

# 셀렉션 정렬 실습

 

2-1 : 제일 작은 수의 index 찾아오고

 

 

---

 

2-2 : 제일 작은 수 맨 앞에 넣어 주기

• 맨 앞이란 매번 0번째가 아니라 값을 넣어줄 맨 앞 값 - ( 1씩늘어나는 값 활용 )
• minIndex도 무조건 0이 아니라 맨앞인 n 번째이다!

 

 

---

 

 

//셀렉션 정렬 해보기
public static void selectrionSort(int[] arr) {

    //한바퀴 제일 작은거 찾기 ( 인덱스 기억 )
    //맨 앞에다가 넣기

    for (int n=0; n < arr.length; n++) {

        int minIdx = n;
        for (int i = 0; i < arr.length; i++) {
            if(arr[minIdx] > arr[i]) {
                //minIdx 갱신
                minIdx = i;
            }
        }//for

        //맨 앞에 넣기
        int temp = arr[minIdx];
        arr[minIdx] = arr[n];
        arr[n]=temp;

    }		
}//method

 

 

 

 

---

 

 

 

 

 

3. 정렬 별 장단점과 시간복잡도

 

 

 

 

---

 

 

 

참고 : 수업내용 + https://coding-factory.tistory.com/

 

 

 

 

 

 

---