/* Quick Sorting.
* Implementation history:.
* 2013-09-15, Mars Fu, first version.
*/ /* [Quicksort Algorithm]
* Published by C.A.R.Hoare,[Comp. J.5(1962),10-15].
*/ #include "stdafx.h" #include "quicksort.h" int
do_quick_sort(void* src, int src_sz, int n, cmp_func cmp, exc_func exchange, dbg_func dbg)
{
const int M = 0;
int i,j,k;
int l,r;
char *kv, *ki, *kj;
static int h = 0; F_S(); if (src == NULL || cmp == NULL || exchange == NULL) return 0;
if (src_sz <= 0 || n <= 0) return 0; Q1:
/* initialize
*/
if (n <= M) {
/* do straight insertion sort
*/
return 1;
}
else {
l = 0;
r = n-1;
} Q2:
/* begine new stage
*/
i = l;
j = r + 1;
kv = (char*)src + l * src_sz; Q3:
do {
/* compare @kv with @ki
*/
do {
++i;
if (i >= j) break;
ki = (char*)src + i * src_sz;
} while (cmp(ki, kv) < 0); /* compare @kv with @kj
*/
do {
--j;
if (j <= i) break;
kj = (char*)src + j * src_sz;
} while (cmp(kv, kj) < 0); /* test i:j
*/
if (j <= i) { /* found the absolute index @j for @kv,do exchanging here and break.
*/
if (j < i) {
kj = (char*)src + j * src_sz;
exchange(kv, kj);
}
else {
/* @i == @j means no need to exchange,having been sorted already.
*/
} if (dbg) dbg(src, n, ++h);
break;
}
else {
ki = (char*)src + i * src_sz;
kj = (char*)src + j * src_sz;
exchange(ki, kj); if (dbg) dbg(src, n, ++h);
}
} while (1); Q4:
/* do the same procedure via recursion with the changed @left or @right.
*/
if(i == j) {
/* the first item is sorted already, move forward 1 item, sort again.
*/
do_quick_sort((char*)src + 1*src_sz, src_sz, n-1, cmp, exchange, dbg);
}
else {
if (j-l > 1) {
do_quick_sort((char*)src + l*src_sz, src_sz, j-l, cmp, exchange, dbg);
} if (r-j > 1) {
do_quick_sort((char*)src + i*src_sz, src_sz, r-j, cmp, exchange, dbg);
}
} END:
F_E();
return 1;
} #ifdef QUICK_SORT_DEBUG static int
int_increasing_cmp(void* lv, void* rv)
{
int tmp_lv, tmp_rv; tmp_lv = *(int*)lv;
tmp_rv = *(int*)rv; return (tmp_lv - tmp_rv);
} static void
exchange_int_item(void* lv, void* rv)
{
int tmp_lv, tmp_rv; tmp_lv = *(int*)lv;
tmp_rv = *(int*)rv; *(int*)lv = *(int*)rv;
*(int*)rv = tmp_lv;
} static void
debug_func(void*src, int n, int h)
{
int i; debug("%d-sort:\r\n----\r\n", h);
for (i = 0; i < n; ++i) {
debug("%d ", *((int*)src + i));
}
debug("\r\n----\r\n");
} int
main(int argc, char* argv[])
{
int i;
int cnt;
const int int_items[] = { 503, 87, 512, 61, 908, 170, 897, 275,
653, 426, 154, 509, 612, 677, 765, 703
};
int ret; debug("[Testing quick sort].. \r\n"); cnt = sizeof(int_items)/sizeof(int_items[0]); debug("src database:\r\n----\r\n");
for (i = 0; i < cnt; ++i) {
debug("%d ", int_items[i]);
}
debug("\r\n----\r\n"); ret = do_quick_sort((void*)int_items, sizeof(int), cnt,
int_increasing_cmp, exchange_int_item, debug_func);
if (!ret) {
debug("failed. \r\n");
goto END;
} debug("dst database:\r\n----\r\n");
for (i = 0; i < cnt; ++i) {
debug("%d ", int_items[i]);
}
debug("\r\n----\r\n"); debug("\r\n"); debug("[Testing quick sort].. done. \r\n"); END:
while(1);
return 0;
} #endif /* QUICK_SORT_DEBUG */
#ifndef __QUICKSORT_H__
#define __QUICKSORT_H__ #define QUICK_SORT_DEBUG typedef int(*cmp_func)(void*, void*);
typedef void (*exc_func)(void*, void*);
typedef void (*dbg_func)(void*, int, int); int do_quick_sort(void* src, int src_sz, int n, cmp_func cmp, exc_func exchange, dbg_func dbg); #endif /* __QUICKSORT_H__ */
#pragma once #include <windows.h>
#ifdef _WIN32
#define msleep(x) Sleep(x)
#endif #include <stdio.h>
#include <tchar.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include <math.h> #define MY_DEBUG
#ifdef MY_DEBUG
#define debug printf
#else
#define debug(x,argc, __VA_ARGS__) ;
#endif /* MY_DEBUG */ #define F_S() debug("[%s]..\r\n", __FUNCTION__)
#define F_E() debug("[%s]..done. \r\n", __FUNCTION__)
Mars
Sep 15th, 2013