[ 정렬 ] 🔎BubbleSort / MergeSort / sort() 사용법

 

 

 

 

정렬 알고리즘들의 시간 복잡도

 

 

 

 

 

 

 

 

 

 

 

 

✅ 버블 정렬 / Bubble sort O(n^2)

 

☑️ 인접한 두 원소를 비교해 swap !

(오름차순 기준) 가장 큰 원소부터 오른쪽 끝에 배치

버블 정렬 예시

 

버블 정렬 C++ 코드

void bubbleSort(vector<int>& arr) {
	for(int i=0; i<arr.size()-1; i++) {
    	for(int j=i; j<arr.size()-i-1; j++) {
			if(arr[j]>arr[j+1]) {
				swap(arr[j], arr[j+1]);
            }
        }
    }
}

 

 

향상된 버블 정렬

한 바퀴 쭉 훑었을 때 swap이 한 번도 일어나지 않았다면,

이미 정렬이 완료된 것이므로, return 해버리기!

void bubbleSort2 (vector<int>& arr) {
    for(int i=0; i<arr.size()-1; i++) {
    	bool is_swap = false;

		for(int j=i+1; j<arr.size()-i-1; j++) {
			if(arr[j]>arr[j+1]) {
            	swap(arr[j], arr[j+1]);
                is_swap = true;
            }
		}
        
        if(!is_swap) { //is_swap이 false라면, 모두 정렬된 것이므로 return!
			return;
		}
    }
}

 

 

 

 

 

 

 

 

 

 

---

✅ 합병 정렬 / Merge sort O(nlogn)

 

☑️ 분할 정복 방식의 알고리즘 !

반으로 나누기 - 정렬 - 다시 합치기

새로 담을 배열이 필요!

합병 정렬 예시

합병 정렬 예시

 

 

* 분할 정복

한 번에 해결할 수 없는 문제를 작은 문제로 분할해 해결하는 알고리즘

- 주로 재귀함수로 구현

- 문제 분할 -> 쪼갠 작은 문제 해결 -> 해결된 조각들을 다시 합침

 

 

 

 

 

합병 정렬 예시 코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> sorted;

void merge(vector<int>& arr, int left, int mid, int right) {
    
    int pl=left, pr=mid+1, idx=left;
    
    while(pl<=mid && pr<=right) {
        if(arr[pl]<arr[pr]) {
            sorted[idx++]=arr[pl++];
        }
        else{
            sorted[idx++]=arr[pr++];    
        }
    } 
    
    while(pl<=mid){
        sorted[idx++] = arr[pl++];
    }
    while(pr<=right){
        sorted[idx++]=arr[pr++];
    }
    
    //정렬된 배열 원 배열에 넣기.
    for(int i=left; i<=right; i++) {
        arr[i]=sorted[i];
    }
    
}

void mergeSort(vector<int>& arr, int left, int right) {
	if(left<right){
	    int mid = (left+right)/2;
	    mergeSort(arr, left, mid);
	    mergeSort(arr, mid+1, right);
	    
	    merge(arr, left, mid, right);

	}
}

int main()
{
    int n;
    cin>>n;
    vector<int> arr(n);
    
    //문자열 할당. assign 함수
    //백터의 범위 내에서 해당 값으로 초기화
    sorted.assign(n,0);
    
    for(int i=0; i<n; i++) {
        cin >> arr[i];
    }
    
    mergeSort(arr,0,n-1);
    
    for(int i=0; i<n; i++) {
        cout << arr[i] << "\n";
    }
    
    return 0;
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

✅ sort() O(nlogn)

 

☑️ c++의 <algorithm> 헤더파일에 포함된 정렬 함수

• 기본적으로 오름차순 / greater<>() 쓰면 내림차순 / 그 밖의 정렬은 comp 정의
• compare가 false를 반환해야 swap됨 !
• 정렬 알고리즘은 그리디 문제에 쓰이는 경우가 많음

앞에서 본 버블, 합병 정렬 등등 정렬 알고리즘은 많다. 그러나, 그냥 sort 함수 쓰자 !

 

* sort (배열 메모리 주소, 끝 메모리 주소)

ex) sort(arr, arr+10);

 

 

 

* 비교함수 / compare

원하는 정렬의 기준을 정의해서 그 기준으로 정렬 !

ex) sort(arr, arr+10, compare);

 

 

 

 

비교함수 예제 (+구조체 활용)

#include <iostream>
#include <vector>

using namespace std;

typedef  struct 사람 {
    string 이름;
    int 나이;
}p;

bool cmp(p a, p b) {
    return a.나이<b.나이;
}


int main()
{
    vector<p> 사람;
    
    //push_back은 vector 끝에 요소를 추가할 때 사용하는 함수
    사람.push_back({"정민",18});
    사람.push_back({"지호",24});
    사람.push_back({"강혁",22});

    sort(사람.begin(), 사람.end(), cmp);
    
    for(int i=0; i<사람.size(); i++) {
        cout << 사람[i].이름 << "\n";
    }
    
    return 0;
}

 

 

 

 

 

sort 함수 쓰는 법 총 정리

//비교함수 정의해두기
cmp() {
	~~~
}

int main() {
	
    vector<int> arr;
    for(int i=0; i<10; i++) {
		arr.push_back(rand()%10);
	}
    
    //기본은 오름차순 정렬
    sort(arr.begin(), v.end());
    //이래도 오름차순 정렬
    sort(arr.begin(), v.end(), less<int>);
    
    
    //내림차순 정렬
	sort(arr.begin(), v.end(), greater<int>());
    
    //비교함수 넣어 정렬
	sort(arr.begin(), v.end(), cmp);

	return 0;
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---