버블 정렬(Bubble Sort)

더보기 
void optimizedBubbleSort(int a[], int n){
    for (int i = 0; i < n-1; ++i) {
        for (int j = 0; j < n-1-i; ++j)
            if (n[j] > n[j+1]) swap(n[j], n[j+1]);
    }
}

크거나 작은 수를 배열의 뒤쪽으로 밀면서 정렬한다. 시간 복잡도는 O(N^2)이다.

 

 

삽입 정렬(Insertion Sort)

더보기 
void insertionSort(int a[], int n) {
    for (int i = 1; i < n; ++i) {
        int current = a[i];
        int prev = i - 1;
        
        while (0 <= prev && a[prev] > current) {
            a[prev + 1] = a[prev];
            --prev;
        }
        a[prev + 1] = current;
    }
}

배열을 정렬된 값들, 정렬되지 않은 값들의 영역으로 분리하여 앞으로 끌고오며 값을 당겨온다.

시간 복잡도는 O(N^2)이다. 또한 stable sort이다.

 

 

선택 정렬(Selection Sort)

더보기 
void selectionSort(int a[], int n) {
    for (int i = 0; i < n-1; ++i) {
        for (int j = i + 1; j < n; ++j)
            if (a[i] > a[j]) swap(a[i], a[j]);
    }
}

버블 정렬과 더불어 가장 기본적인 정렬이고 버블 정렬과 다르게 정렬된 값을 앞에서부터 채워나간다.

시간 복잡도는 O(N^2)이다.

 

 

계수 정렬(Counting Sort)

더보기 
void countingSort(int a[], int n) {
    int largest = -1; // 오름차순, 내림차순과 값의 범위에 따라 결정
    
    for (int i = 0; i < n; ++i)
        largest = max(largest, a[i]);
    
    vector<int> freq(largest+1, 0);
    
    for (int i = 0; i < n; ++i) {
        freq[a[i]]++;
    }
        
    int j = 0;
    for (int i = 0; i <= largest; ++i) {
        while (freq[i]-- > 0) {
            a[j] = i;
            ++j;
        }
    }
}

정렬될 값의 범위(Range)가 넓지 않고 범위를 알고 있을 때 유용하게 사용할 수 있다.

범위를 정확히 알지 못하더라도 최대값을 구해서 벡터를 사용하면 된다.

시간 복잡도는 O(Range + N)이다.

저작자표시

'이론 > 자료구조&알고리즘' 카테고리의 다른 글

Vector Data Structure  (0) 2023.02.08
Pointers & Dynamic Memory  (0) 2023.02.07
2D Arrays  (0) 2023.02.07
Character Arrays/Strings  (0) 2023.02.03
Arrays  (0) 2023.02.02

연속된 메모리 공간에 할당되고 모두 동일한 타입으로 사용된다.

 

void func(int arr[]); // sizeof(arr) : 8
// void func(int* arr);

int main() {
    int arr[] = { 1, 2, 3, 4, 5 }; // sizeof(arr) : 20
    func(arr);
    
    return 0;
}

배열을 함수의 인수로 넘겨주면 주소값이 전달되기 때문에 포인터의 크기가 나온다.

인수가 배열이라는 것을 명시적으로 알려줄 뿐 사실은 포인터와 완전히 동일하다.

 

◾ 배열의 요소를 뒤집을 때 투 포인터를 사용하면 시간 복잡도는 O(N/2), 공간 복잡도는 그대로이다.

 

부분 배열

◾ 배열의 크기가 N이라면 부분 배열들의 개수는 N^3에 근접한다.

◾ 3중 for문을 사용하면 배열의 부분 배열들을 출력할 수 있다. (i=0<n, j=0<n, k=i<=j)

 

부분 배열의 합 : 브루트 포스

더보기 
int largestSubarraySum(int arr[], int n) {
    int largestSum = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            int subarraySum = 0;
            for (int k = i; k <= j; ++k) {
                subarraySum += arr[k];
            }
            largestSum = max(largestSum, subarraySum);
        }
    }
    return largestSum;
}

완전 탐색에 의해 계산되고 공간 복잡도는 O(1), 시간 복잡도는 O(N^3)이다.

반복문을 두개로 줄일 수 있으므로 O(N^2)까지 낮출 수 있다.

 

부분 배열의 합 : 누적합

더보기 
int largestSubarraySum(int arr[], int n) {
    vector<int> prefix(n, 0);
    prefix[0] = arr[0];
    
    for (int = 1; i < n; ++i)
        prefix[i] = prefix[i-1] + arr[i];
        
    int largestSum = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            int subarraySub = i > 0 ? prefix[j] - prefix[i-1] : prefix[j];            
            largestSum = max(largestSum, subarraySum);
        }
    }
    return largestSum;
}

공간 복잡도는 O(N), 시간 복잡도는 O(N+N^2) = O(N^2)이다.

 

부분 배열의 합 : Kadane 알고리즘

더보기 
int largestSubarraySum(int arr[], int n) {
    int currentSum = arr[0];
    int largestSum = arr[0];
    
    for (int i = 1; i < n; ++i) {
        currentSum = max(currentSum + arr[i], arr[i]);
        largestSum = max(largestSum, currentSum);
    }
    
    return largestSum;
}

현재 누적합과 최대 누적합을 별도로 관리하여 선형으로 계산해나간다.

공간 복잡도는 O(1), 시간 복잡도는 O(N)이다.

저작자표시

'이론 > 자료구조&알고리즘' 카테고리의 다른 글

Vector Data Structure  (0) 2023.02.08
Pointers & Dynamic Memory  (0) 2023.02.07
2D Arrays  (0) 2023.02.07
Character Arrays/Strings  (0) 2023.02.03
Basic Sorting Algorithms  (0) 2023.02.03

+ Recent posts

티스토리툴바