Quick_Sort 문제 풀기(Divide and conquer)

https://www.geeksforgeeks.org/problems/quick-sort/1

Quick Sort | Practice | GeeksforGeeks

Quick Sort is a Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot.
Given an array arr[], its starting position is low (the index of the array) and its ending position is high(the index of the array).

Note: The low and high are inclusive.

Implement the partition() and quickSort() functions to sort the array.

Example 1:

Input: 
N = 5 
arr[] = { 4, 1, 3, 9, 7}
Output:
1 3 4 7 9

Example 2:

Input: 
N = 9
arr[] = { 2, 1, 6, 10, 4, 1, 3, 9, 7}
Output:
1 1 2 3 4 6 7 9 10

Your Task: 
You don't need to read input or print anything. Your task is to complete the functions partition()  and quickSort() which takes the array arr[], low and high as input parameters and partitions the array. Consider the last element as the pivot such that all the elements less than(or equal to) the pivot lie before it and the elements greater than it lie after the pivot.

Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(logN)

Constraints:
1 <= N <= 103
1 <= arr[i] <= 104

---

요번엔 좀 다른 플렛폼에서 문제를 가져와봤다. GeeksforGeeks 라는 녀석인데,

 

사실 얘네는 web site 내부에 각종 광고배너가 너무 많아서 애용하진 않는 편이다..

 

어쨌든, Divide and Conquer을 이용해서 array를 오름차순으로 정렬하는 Quick sort 함수를 만들어보자.

 

1. Python

초장부터 감이 안 잡혀서 gpt 도움을 받았다..

class Solution:
    # Function to sort a list using quick sort algorithm.
    def quickSort(self, arr, low, high):
        if low < high:
            # Partition the array and get the pivot index
            pi = self.partition(arr, low, high)
            
            # Recursively sort elements before and after partition
            self.quickSort(arr, low, pi - 1)
            self.quickSort(arr, pi + 1, high)
    
    # Function to partition the array using the last element as pivot
    def partition(self, arr, low, high):
        pivot = arr[high]  # Choosing the last element as the pivot
        i = low - 1  # Index of smaller element
        
        # Traverse through the array from low to high-1
        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]  # Swap elements
        
        # Swap the pivot element with the element at i+1
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        
        return i + 1  # Return the pivot index

 

2. C

swap 함수를 좀 만들어 준다.

 

void swap(int* a, int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
void quickSort(int arr[], int low, int high)
{    // code here
    if(low<high){
        int pi = partition(arr,low,high);
        quickSort(arr,low,pi-1);
        quickSort(arr,pi+1,high);
    }
    return;
}
int partition (int arr[], int low, int high)
{
   // Your code here
    int pivot = arr[high];
    int i = low - 1;
    for(int j=low;j<high;j++){
        if(arr[j]<pivot){
            i++;
            swap(arr[i],arr[j]);
        }
    }
    swap(arr[i+1],arr[high]);
    return i+1;
}

 

솔직히 나한텐 좀 어려운 개념이다 Quick Sort..

 

맨 땅에서 이 정도 퀄리티를 만들어 낼 수 있을런지;; 자신이 없다 자신이 ㅠ

 

 

3. C++

C++엔 swap함수가 포함되어 있는 헤더파일이 있다.

#include <iostream>
#include <utility>  // std::swap

void quickSort(int arr[], int low, int high);
int partition(int arr[], int low, int high);

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    std::cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // Pivot is the last element
    int i = low - 1;  // Index of smaller element

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);  // Using std::swap to swap elements
        }
    }
    std::swap(arr[i + 1], arr[high]);  // Place pivot in correct position
    return i + 1;
}

 

쫄지 말자.

 

조금씩 나아지는 건 나일테니