一个数组中的元素被分为low, medium, high三类,实现一个排序算法,将该数组按照不同的类别进行排序。规则为low < medium < high.

Example:

Input:

The input array is ['g', 'n', 'e', 'c', 't', 'z', 'o', 'f'], and the elment sorted into 3 categories as below:

low: a-h
med: i-p
high: q-z

Output:

['c', 'e', 'g', 'f', 'n', 'o', 'z', 't']

function provided listed below, and its algorithm complexityis O(n).

bool islow(char c);
bool ismed(char c);
bool ishigh(char c);

Resolution:

You can sort any array with famous sorting algorithm, like bubblesort, insertsort, quicksort and etc. However, any sorting algorithm,  based on comparation of element, can’t do better than O(nlogn) without extra memory.

The element in the array has partitioned into 3 categories, which means this array only have three different element. Therefore, You do not need to care about the ranking of element in same categories.  So, Sorting the array could use 2 partition algorithm in quicksort. First, select an element in medium category as pivot, after partition, the left side of element in low category, and the right side is mixer of medium & high. Then, select a high one, partition the latter part of array. You will get the result.  and the complexity of algorithm is O(n).

Code:


#include <stdio.h>
#include <stdlib.h>
void swap(char* array, int i, int j) {
    char tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

bool compare_char(char a, char b) {
    if(islow(a) && (ismed(b) || ishigh(b))) {
        return true;
    }

    if(ismed(a) && ishigh(b)) {
        return true;
    }

    return false;
}

int partition(char* array, int left, int right, int pivot_idx) {
    swap(array, pivot_idx, right);
    char pivot = array[right];
    int save = left;
    int i = 0;
    for(int i = left; i < right; i++) {
        if(compare_char(array[i], pivot)) {
            swap(array, i, save);
            save++;
        }
    }
    swap(array, save, right);

    return save;
}

int get_med_idx(char *array, int size)
{
    for(int i = 0; i < size ; i++) {
            if(ismed(array[i])) {
                  return i;
            }
    }

    return -1;
}

int get_high_idx(char *array, int size)
{
    for(int i = 0; i < size ; i++) {
            if(ishigh(array[i])) {
                  return i;
            }
    }
    return -1;
}

void sort_by_category(char *array, int size) {
     if(size <= 0) {          return;      }            //partition array with med_idx      //output array likes [{low}, {med, high}]              int pos = 0;      int med_idx = get_med_idx(array, size);      if(med_idx >= 0) {
           pos = partition(array, 0 , size - 1, med_idx);
     }

     //partition the later part array {med,high} with high_idx
     //output array like [{low}, {med}, {high}]
     int high_idx = get_high_idx(array + pos, size - pos);
     if(high_idx >= 0) {
           pos = partition(array + pos, 0 , size - pos - 1 , high_idx);
     }
}
转载请注明来源:Leoncom-《Sorting an array whose elements partition into three categories》
Trackback

no comment untill now

Add your comment now