Sắp xếp: cách sắp xếp một mảng chứa 3 loại số

Question

Ví dụ: int A[] = {3,2,1,2,3,2,1,3,1,2,3};

Cách sắp xếp mảng này hiệu quả?

Đây là cuộc phỏng vấn xin việc, tôi chỉ cần một mã giả.

Answer 1

Vấn đề: Bạn có n xô, mỗi thùng chứa một đồng xu, giá trị của đồng tiền có thể là 5 hoặc 10 hoặc 20. bạn phải sắp xếp các thùng dưới hạn chế này: 1. Bạn có thể sử dụng 2 chức năng này chỉ: SwitchBaskets (Basket1, Basket2) - chuyển 2 giỏ GetCoinValue (Basket1) - trả về Coin Value trong giỏ đã chọn 2. bạn không thể xác định mảng kích thước n 3. sử dụng chức năng chuyển đổi càng ít càng tốt.

Giải pháp mã giả đơn giản của tôi, có thể được triển khai bằng bất kỳ ngôn ngữ nào có độ phức tạp O (n).

tôi sẽ chọn đồng xu từ giỏ 1) nếu nó là 5 - đẩy nó để là người đầu tiên, 2) nếu nó được 20- đẩy nó để là người cuối cùng, 3) Nếu 10 - rời khỏi nó, nơi nó Là. 4) và nhìn vào thùng tiếp theo trong dòng.

Edit:nếu bạn không thể đẩy các yếu tố về vị trí đầu tiên hoặc cuối cùng sau đó Merge sort sẽ là lý tưởng để thực hiện cướp biển. Đây là cách hoạt động:

Sắp xếp hợp nhất tận dụng lợi thế của việc dễ dàng hợp nhất các danh sách đã sắp xếp vào danh sách được sắp xếp mới. Nó bắt đầu bằng cách so sánh hai phần tử (tức là, 1 với 2, rồi 3 với 4 ...) và hoán đổi chúng nếu lần đầu tiên đến sau phần tử thứ hai. Sau đó, nó hợp nhất mỗi danh sách kết quả của hai danh sách thành bốn danh sách, sau đó hợp nhất các danh sách đó với bốn danh sách, v.v. cho đến khi hai danh sách cuối cùng được hợp nhất vào danh sách được sắp xếp cuối cùng. Trong số các thuật toán được mô tả ở đây, đây là lần đầu tiên có quy mô tốt với các danh sách rất lớn, vì thời gian chạy trường hợp xấu nhất của nó là O (n log n). Hợp nhất sắp xếp đã thấy sự gia tăng tương đối phổ biến cho việc triển khai thực tế, được sử dụng cho thói quen sắp xếp tiêu chuẩn trong các ngôn ngữ lập trình

Answer 2

Tôi nghĩ rằng câu hỏi có ý định để bạn sử dụng bucket sort. Trong trường hợp có một số lượng nhỏ các giá trị nhóm sắp xếp có thể nhanh hơn nhiều so với cách nhanh chóng được sử dụng nhanh hơn hoặc hợp nhất.

Answer 3

Bạn đã thử xem wiki chẳng hạn? - http://en.wikipedia.org/wiki/Sorting_algorithm

Answer 4

đếm mỗi số và sau đó tạo mảng mới dựa trên số lượng của họ ... phức tạp trong thời gian O (n)

int counts[3] = {0,0,0}; 
for(int a in A) 
    counts[a-1]++; 
for(int i = 0; i < counts[0]; i++) 
    A[i] = 1; 
for(int i = counts[0]; i < counts[0] + counts[1]; i++) 
    A[i] = 2; 
for(int i = counts[0] + counts[1]; i < counts[0] + counts[1] + counts[2]; i++) 
    A[i] = 3; 

Answer 5

Như robert nêu basketsort (hoặc bucketsort) là tốt nhất trong tình huống này.

Tôi cũng xin nói thêm thuật toán tiếp theo (nó thực sự rất giống với busket loại):

[giả là java-style]

Tạo một chu kỳ HashMap<Integer, Interger> map và Xuyên mảng của bạn:

for (Integer i: array) 
{ 
    Integer value = map.get(i); 
    if (value == null) 
    { 
     map.put(i, 1); 
    } 
    else 
    { 
     map.put(i, value+1); 
    } 
} 

Answer 6

Cách đầy hứa hẹn về cách sắp xếp nó có vẻ là counting sort. Đáng để xem this lecture bởi Richard Buckland, đặc biệt là phần từ 15:20.

Tương tự với loại đếm, nhưng tốt hơn là tạo mảng đại diện cho miền, khởi tạo tất cả các phần tử của nó thành 0 và sau đó lặp qua mảng của bạn và đếm các giá trị này. Một khi bạn biết những giá trị của các giá trị tên miền, bạn có thể viết lại các giá trị của mảng của bạn cho phù hợp. Độ phức tạp của thuật toán như vậy sẽ là O (n).

Đây là mã C++ có hành vi như tôi đã mô tả. phức tạp của nó thực sự là O (2n) mặc dù:

int A[] = {3,2,1,2,3,2,1,3,1,2,3}; 
int domain[4] = {0}; 

// count occurrences of domain values - O(n): 
int size = sizeof(A)/sizeof(int); 
for (int i = 0; i < size; ++i) 
    domain[A[i]]++; 

// rewrite values of the array A accordingly - O(n):  
for (int k = 0, i = 1; i < 4; ++i) 
    for (int j = 0; j < domain[i]; ++j) 
     A[k++] = i; 

Lưu ý, rằng nếu có sự khác biệt lớn giữa các giá trị tên miền, lưu trữ tên miền như một mảng là không hiệu quả. Trong trường hợp đó, bạn nên sử dụng bản đồ (cảm ơn abhinav để chỉ ra nó). Dưới đây là mã C++ sử dụng std::map để lưu trữ giá trị miền - lần xuất hiện đếm cặp:

int A[] = {2000,10000,7,10000,10000,2000,10000,7,7,10000}; 
std::map<int, int> domain; 

// count occurrences of domain values: 
int size = sizeof(A)/sizeof(int); 
for (int i = 0; i < size; ++i) 
{ 
    std::map<int, int>::iterator keyItr = domain.lower_bound(A[i]); 
    if (keyItr != domain.end() && !domain.key_comp()(A[i], keyItr->first)) 
     keyItr->second++; // next occurrence 
    else 
     domain.insert(keyItr, std::pair<int,int>(A[i],1)); // first occurrence 
} 

// rewrite values of the array A accordingly:  
int k = 0; 
for (auto i = domain.begin(); i != domain.end(); ++i) 
    for (int j = 0; j < i->second; ++j) 
     A[k++] = i->first; 

(nếu có một cách làm thế nào để sử dụng std::map trong mã trên hiệu quả hơn, cho tôi biết)

Answer 7

Mã này là đối với C#:

Tuy nhiên, bạn phải xem xét các thuật toán để triển khai nó theo cách không theo ngôn ngữ/không theo khuôn khổ. Như được đề xuất Bucket set có thể là một trong những hiệu quả để đi với. Nếu bạn cung cấp thông tin chi tiết về vấn đề, tôi sẽ cố gắng xem xét giải pháp tốt nhất. Chúc may mắn ...

Đây là mẫu mã trong C#.NET mô tả

int[] intArray = new int[9] {3,2,1,2,3,2,1,3,1 }; 
Array.Sort(intArray); 
// write array 
foreach (int i in intArray) Console.Write("{0}, ", i.ToString()); 

Answer 8

Vấn đề tiêu chuẩn trong khoa học máy tính: Dutch national flag problem Xem liên kết.

Answer 9

Tôi nghĩ rằng tôi đánh giá thấp câu hỏi - bạn chỉ có thể sử dụng không gian O (1) và bạn có thể thay đổi mảng chỉ bằng cách hoán đổi ô. (Vì vậy, bạn có thể sử dụng 2 thao tác trên mảng - trao đổi và nhận được)

Giải pháp của tôi:

Sử dụng 2 con trỏ chỉ số - một cho vị trí của 1, và một cho vị trí của người cuối cùng 2.

Trong giai đoạn i, bạn cho rằng mảng được allready được sắp xếp từ 1 đến i-1, hơn bạn kiểm tra các tế bào thứ i: Nếu A [i] == 3 bạn không làm gì cả. Nếu A [i] == 2 bạn hoán đổi nó với ô sau 2 chỉ mục cuối cùng. Nếu A [i] == 1 bạn hoán đổi nó với ô sau 2 chỉ mục cuối cùng và thay đổi ô sau 2 chỉ mục cuối cùng (có chứa 1) với ô sau chỉ mục 1 cuối cùng.

Đây là ý tưởng chính, bạn cần phải chăm sóc các chi tiết nhỏ. Độ phức tạp tổng thể O (n).

Answer 10

Chỉ cần cho vui, dưới đây là cách bạn sẽ thực hiện "đẩy giá trị đến mép xa", như ElYusubub gợi ý:

sort(array) { 
    a = 0 
    b = array.length 
    # a is the first item which isn't a 1 
    while array[a] == 1 
    a++ 
    # b is the last item which isn't a 3 
    while array[b] == 3 
    b-- 

    # go over all the items from the first non-1 to the last non-3 
    for (i = a; i <= b; i++) 
    # the while loop is because the swap could result in a 3 or a 1 
    while array[i] != 2 
     if array[i] == 1 
     swap(i, a) 
     while array[a] == 1 
      a++ 
     else # array[i] == 3 
     swap(i, b) 
     while array[b] == 3 
      b-- 

Điều này thực sự có thể là một giải pháp tối ưu. Tôi không chắc.

Answer 11

Đây là giải pháp groovy, dựa trên @ElYusubov nhưng thay vì đẩy Bucket (5) để bắt đầu & Bucket (15) để kết thúc. Sử dụng chọn lọc để 5 di chuyển về phía đầu và 15 về phía cuối.

Bất cứ khi nào chúng tôi hoán đổi một xô từ cuối đến vị trí hiện tại, chúng tôi giảm dần, không tăng bộ đếm hiện tại vì chúng tôi cần kiểm tra lại yếu tố.

array = [15,5,10,5,10,10,15,5,15,10,5] 

    def swapBucket(int a, int b) { 

     if (a == b) return; 
     array[a] = array[a] + array[b] 
     array[b] = array[a] - array[b] 
     array[a] = array[a] - array[b] 

    } 

def getBucketValue(int a) { 
    return array[a]; 
} 

def start = 0, end = array.size() -1, counter = 0; 
// we can probably do away with this start,end but it helps when already sorted. 

// start - first bucket from left which is not 5 
while (start < end) { 

    if (getBucketValue(start) != 5) break; 
    start++; 

}  

// end - first bucket from right whichis not 15 
while (end > start) { 

    if (getBucketValue(end) != 15) break; 
    end--; 

} 

// already sorted when end = 1 { 1...size-1 are Buck(15) } or start = end-1  

for (counter = start; counter < end;) { 

    def value = getBucketValue(counter) 

    if (value == 5) { swapBucket(start, counter); start++; counter++;} 
    else if (value == 15) { swapBucket(end, counter); end--; } // do not inc counter 
    else { counter++; } 

} 

for (key in array) { print " ${key} " } 

Answer 12

Cho phép giải quyết sự cố chúng tôi chỉ có hai số trong mảng. [1,2,1,2,2,2,1,1]

Chúng tôi có thể sắp xếp theo một lần o (n) với hoán đổi phút nếu; Chúng tôi bắt đầu hai con trỏ từ trái sang phải cho đến khi chúng gặp nhau. Hoán đổi phần tử bên trái với phần tử phải nếu trái lớn hơn. (sắp xếp tăng dần)

Chúng tôi có thể thực hiện một thẻ khác, cho ba số (vé k-1). Trong một, chúng tôi di chuyển 1 đến vị trí cuối cùng của họ và trong vượt qua 2, chúng tôi di chuyển 2.

def start = 0, end = array.size() - 1; 

// Pass 1, move lowest order element (1) to their final position 
while (start < end) { 
    // first element from left which is not 1 
    for (; Array[start] == 1 && start < end ; start++); 
    // first element from right which IS 1 
    for (; Array[end] != 1 && start < end ; end--); 

    if (start < end) swap(start, end); 
}  

// In second pass we can do 10,15 

// We can extend this using recurion, for sorting domain = k, we need k-1 recurions 

Answer 13

Điều này có thể được thực hiện rất dễ dàng sử dụng ->

Dutch Cờ quốc gia thuật toán http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

thay vì sử dụng 1,2,3 mang nó như 0,1,2

Answer 14

//Bubble sort for unsorted array - algorithm 
public void bubleSort(int arr[], int n) { //n is the length of an array 
    int temp; 
    for(int i = 0; i <= n-2; i++){ 
     for(int j = 0; j <= (n-2-i); j++){ 
      if(arr[j] > arr[j +1]){ 
       temp = arr[j]; 
       arr[j] = arr[j +1]; 
       arr[j + 1] = temp; 

      } 
     } 

    } 

Answer 15

def DNF(input,length): 
    high = length - 1 
    p = 0 
    i = 0 
    while i <= high: 
      if input[i] == 0: 
        input[i],input[p]=input[p],input[i] 
        p = p+1 
        i = i+1 
      elif input[i] == 2: 
        input[i],input[high]=input[high],input[i] 
        high = high-1 
      else: 
        i = i+1 
input = [0,1,2,2,1,0] 
print "input: ", input 
DNF(input,len(input)) 
print "output: ", input