Hướng dẫn thuật toán Quicksort

#1

Trong video này Đạt giới thiệu thuật toán QuickSort và code bằng Python/C, hướng dẫn cơ bản về thuật toán.

Code Python

def partition(arr, lo, hi):
    pivot = arr[hi]
    small_i = lo - 1
    for i in range(lo, hi): # chay tu low den high (khong tinh high)
        if arr[i] <= pivot:
            small_i += 1
            arr[small_i], arr[i] = arr[i], arr[small_i]
    small_i += 1
    arr[small_i], arr[hi] = arr[hi], arr[small_i]
    return small_i

def quicksort(arr, lo, hi):
    if lo < hi:
        pivot = partition(arr, lo, hi)
        quicksort(arr, lo, pivot - 1)
        quicksort(arr, pivot + 1, hi)

input_arr = [10, 80, 30, 90, 40, 50, 70]
print "input array {}\n".format(input_arr)
quicksort(input_arr, 0, len(input_arr) - 1)
print "sorted array ", input_arr

Code C

#include "stdio.h"

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void print_array(int *arr, int size) {
    int i = 0;
    for(; i < size; ++i){
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int partition(int *arr, int lo, int hi) {
    int pivot = arr[hi];
    int si = lo - 1;
    int j;
    for(j = lo; j <= hi - 1; ++j) {
        if (arr[j] <= pivot) {
            si++;
            swap(&arr[si], &arr[j]);
        }
    }
    si++;
    swap(&arr[si], &arr[hi]);
    return si;
}

void quicksort(int *arr, int lo, int hi) {
    if (lo < hi) {
        int pivot = partition(arr, lo, hi);
        quicksort(arr, lo, pivot - 1);
        quicksort(arr, pivot + 1, hi);
    }
}


int main() {
    int arr[] = {10, 80, 30, 90, 40, 50, 70};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("before ");
    print_array(arr, n);
    quicksort(arr, 0, n-1);
    printf("after ");
    print_array(arr, n);
}

Code Python with log

def partition(arr, lo, hi):
    pivot = arr[hi]
    print "new pivot [{}], lo: {}, hi: {}".format(pivot, lo, hi)
    small_i = lo - 1
    for i in range(lo, hi):
        if arr[i] <= pivot:
            small_i += 1
            print_quicksort(arr, hi, small_i, i, lo, hi)
            arr[small_i], arr[i] = arr[i], arr[small_i]
            print "after swap: {}\n".format(arr)

    small_i += 1
    arr[small_i], arr[hi] = arr[hi], arr[small_i]
    return small_i

def quicksort(arr, lo, hi):
    if lo < hi:
        pivot = partition(arr, lo, hi)
        quicksort(arr, lo, pivot - 1)
        quicksort(arr, pivot + 1, hi)

def print_quicksort(arr, pivot_index, small_i, index, lo, hi):
    print "lo: {}, hi: {}, small index: {}, index: {}".format(lo, hi, small_i, index)
    output = ""
    for i, value in enumerate(arr):
        if i == lo:
            output += "("
        if i == hi:
            output += ")"
        if i == pivot_index:
            output += "[{}] ".format(value)
        elif i == small_i:
            output += "{}-> ".format(value)
        elif i == index:
            output += "<-{} ".format(value)
        else:
            output += "{} ".format(value)
    print output


input_arr = [10, 80, 30, 90, 40, 50, 70]
print "input array {}\n".format(input_arr)
quicksort(input_arr, 0, len(input_arr) - 1)
print "sorted array ", input_arr
8 Likes
#2

Cảm ơn anh!! Khi học về cái này em cũng hiểu, nhưng khi có cái vid này mới hiểu hết được cái cách nó hoạt động :))

3 Likes
#3

a Đạt làm khoá học chuyên sâu CTDL & GT đi anh ơi :slight_smile:

2 Likes
#4

Trước e học quicksort bằng cái này, cũng dễ hiểu.
http://interactivepython.org/courselib/static/pythonds/SortSearch/TheQuickSort.html

1 Like
#5

Không có thời gian em ơi, lâu lâu anh rảnh thì làm một cái vậy thôi. Chứ không còn thời gian để tập trung làm một loạt bài được :frowning:

3 Likes
#6

em ko hiểu cái này, các anh có thể giúp em tại sao ko đặt int si = lo; và sửa code thành như này!

1 Like
#7

Em code lại như vậy cũng được

2 Likes
#8

vâng, em thấy nắm chắc phần đó là code lên 1 tầm cao mới rồi =))

#9

Hay (:smiley:) ---- 20 characters

#11

Cảm ơn anh vì bài hướng dẫn. Nhân tiện bác nào rảnh xem hộ em sai chỗ nào đc k nhỉ.
Code java các bác ạ.

public class QuickSort {
    public static void Sort(int[] a, int left, int right){
        int i = left+1;
        int j = right;
        if (left<right){
            do {
                while (a[i] <= a[left] && i <= right) ++i;
                while (a[j] > a[left]) --j;
                if (i < j){
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
                for (int data:a){
                    System.out.print(data + " ");
                }
                System.out.println();
            }while(i < j);
            int temp = a[left];
            a[left] = a[j];
            a[j] = temp;
            if (left < j-1) Sort(a,left,j-1);
            if (j+1 < right) Sort(a,j+1,right);
        }
    }

    public static void main(String[] args){
        int[] a = {5,7,2,3,123};
        for (int data:a){
            System.out.print(data + " ");
        }
        System.out.println("\n-------");
        Sort(a,0,a.length-1);
    }
}
#12

hay quá anh Đạt -.-
Anh làm thêm vài video CTDL&GT thì hay quá

#13

Dùng đệ quy mà độ phức tạp của nó vẫn là O(N) hả anh Đạt @ltd .

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?