Search
 
 

Display results as :
 


Rechercher Advanced Search

Latest topics
» NewBlueFx TotalFX Windows-FL | 1.11 GB
Tue Dec 17, 2013 12:42 pm by titquarra

» NewBlueFx TotalFX Windows-FL | 1.11 GB
Tue Dec 17, 2013 12:42 pm by titquarra

» Celebrity.Sex.Tape.UNCUT.&.UNRATED.2012.720p.BRrip.x264.YIFY.mp4
Tue Dec 17, 2013 8:32 am by titquarra

» Maya Autodesk Personal Learning Edition 8.5
Tue Dec 17, 2013 7:47 am by titquarra

» Tuyệt Kỹ Đong Giai Chân Kinh (tuyệt Kỹ cua trai)
Thu Aug 23, 2012 5:38 am by Admin

» Tuyệt kỹ cua giai
Thu Aug 23, 2012 5:36 am by Admin

» NETCAT.........
Mon Aug 13, 2012 6:35 am by Admin

» Bảo mật CSDL bằng phương pháp mã hóa.
Tue Apr 17, 2012 10:04 pm by Admin

» Hàm mã hóa MD5 bằng JavaScript
Tue Apr 17, 2012 10:03 pm by Admin

Shopmotion


Affiliates
free forum


Quick sort

View previous topic View next topic Go down

Quick sort

Post  Admin on Sun Jun 12, 2011 9:51 am

Đây là giả thuật sắp xếp nhanh, chỉ tốn O(nlogn). Cài đặt của giả thuật tương đối phức tạp. Chúng ta cần chú ý đến:

Pivot: ta gọi là chốt
Partition: Gọi là điểm phân hoạch


Đối với giải thuật này, chúng ta xem 1 mảng 1 phần tử hay mảng có tất cả phần tử giống nhau là một mảng có thứ tự. Ta sẽ chi mảng thành 2 mảng con: Trái và phải. Sắp xếp 2 mảng con, và cứ như thế cho đến khi mảng còn 1 phần tử. Nếu mảng Trái đã có thứ tự và mảng phải cũng có thứ tự thì mảng của chúng ta đã là mảng có thứ tự.

A = {59, 31, 12, 33, 27, 97, 91, 19, 18, 63 }

Bước 1: Tìm chốt: Chốt là phần tử lớn nhất trong 2 phần tử khác nhau đầu tiên của mảng. Nếu mảng có 1 phần tử tất cả phần tử bằng nhau sẽ không có chốt:
Chốt của mảng trên la 59 (vị trí 0).
VD:
+ 1, 1, 5, 3, 2 -> chốt sẽ là 5
+ 5, 5, 5, 3, 1, 2, 3 -> chốt là 5
+ 6 -> không có chốt
+ 7, 7, 7, 7 -> không có chốt

Bước 2: Tìm điểm phân hoạch:
+ Dùng 2 cờ: L (trái) và R (Phải)
+ L chạy từ trái qua, dừng lại khi gặp phần tử >= pivot
+ R chạy từ phải qua, dừng lại khi gặp phần tử < pivot
+ Tại điểm dùng: Nếu L < R : Chúng ta sẽ swap A[L] và A[R]
+ Dừng lại khi L > R
+ Partition sẽ là L. Đây sẽ là chỉ số đầu tiên của mảng bên phải
VD: với mảng A = {59, 31, 12, 33, 27, 97, 91, 19, 18, 63 }
PivotLey = 59
L = 0, R = 9:
b1. L dừng lại tại vị trí 0: vì A[L] >= pivot, R dừng lại tại vị trí 8, vì A[R] = 18 < pivot.
Swap: 18, 31, 12, 33, 27, 97, 91, 19, 59, 63
b2, tiếp tục cho đến khi L > R
Bước 3: Lặp lại như thế (Dùng đệ qui)

Code:
// Tìm chốt
public int findPivot(int i, int j, int[] array) {
        if (array.length == 1) {
            return -1;
        }
        int k = i + 1;
        int pivot = array[i];

        while ((k <= j) && (array[k] == pivot)) {
            k++;
        }
        if (k > j) {
            return -1;
        }
        if (array[k] > pivot) {
            return k;
        } else {
            return i;
        }
    }

    // Tìm partition
    public int pointPartition(int i, int j, int pivotKey, int[] array) {
        int partition = -1;

        int L = i;
        int R = j;
        while (L <= R) {
            while (array[L] < pivotKey)
                L++;
            while (array[R] >= pivotKey)
                R--;
            if (L < R) {
                int temp = array[L];
                array[L] = array[R];
                array[R] = temp;
            }
        }
        partition = L;
        return partition;
       
    }

  // Sắp xếp
    public void quickSort(int i, int j, int[] array) {
        int pivot = findPivot(i, j, array);
        if (pivot == -1)
            return;
        int partition = pointPartition(i, j, array[pivot], array);
        quickSort(i, partition - 1, array);
        quickSort(partition, j, array);
    }

  // Test:

  quickSort(0, array.length - 1, array);

Admin
Admin

Tổng số bài gửi : 782
Join date : 2009-08-15

View user profile http://hackis.forumotion.com

Back to top Go down

View previous topic View next topic Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum