Skip to content

Instantly share code, notes, and snippets.

@wtsnjp wtsnjp/quicksort.c

Last active Jul 13, 2020
Embed
What would you like to do?
/*
*
* compile: gcc quicksort.c
* test: ./a.out
*
*/
#include <stdio.h>
enum { SIZE = 9 };
void quicksort(int *target, int left, int right) {
if(left >= right) return;
int i = left, j = right;
int tmp, pivot = target[i];
for(;;) {
while(target[i] < pivot) i++;
while(pivot < target[j]) j--;
if(i >= j) break;
tmp = target[i]; target[i] = target[j]; target[j] = tmp;
i++; j--;
}
quicksort(target, left, i-1);
quicksort(target, j+1, right);
}
int main() {
int i, array[SIZE] = { 2, 6, 3, 8, 5, 4, 1, 9, 7 };
quicksort(array, 0, SIZE-1);
for(i=0; i<SIZE; i++)
printf("%d ", array[i]);
printf("\n");
}
%
% test: latex quicksrot.tex
%
\makeatletter
% new if and new counts
\newif\if@q@loop@
\newcount\q@i
\newcount\q@j
\newcount\q@pivot
% macros for array
\def\array#1#2{\csname #1@#2\endcsname}
\def\defarray#1#2#3{\expandafter\xdef\csname #1@#2\endcsname{#3}}
% quick sort
\def\quicksort#1#2#3{% #1: array name, #2: left, #3:right
\ifnum#2<#3\relax
\bgroup
\q@i#2\q@j#3\relax
\q@pivot\array{#1}{\the\q@i}%
\@q@loop@true
\@whilesw\if@q@loop@\fi{%
\@whilenum\array{#1}{\the\q@i}<\q@pivot\do{\advance\q@i\@ne}%
\@whilenum\q@pivot<\array{#1}{\the\q@j}\do{\advance\q@j\m@ne}%
\ifnum\q@i<\q@j
\edef\q@tmp{\array{#1}{\the\q@i}}%
\defarray{#1}{\the\q@i}{\array{#1}{\the\q@j}}%
\defarray{#1}{\the\q@j}{\q@tmp}%
\advance\q@i\@ne\advance\q@j\m@ne
\else
\@q@loop@false
\fi}%
\advance\q@i\m@ne\advance\q@j\@ne
\edef\q@right{\the\q@i}%
\quicksort{#1}{#2}{\q@right}%
\edef\q@left{\the\q@j}%
\quicksort{#1}{\q@left}{#3}%
\egroup
\fi}
% test
\def\numlist{2,6,3,8,5,4,1,9,7}
\@tempcnta\z@\@tempcntb\z@
\@for\member:=\numlist\do{%
\defarray{test}{\the\@tempcnta}{\member}%
\advance\@tempcnta\@ne}
\quicksort{test}{0}{8}
\typeout{Result:}
\@whilenum\@tempcnta>\@tempcntb\do{%
\message{\array{test}{\the\@tempcntb}}%
\advance\@tempcntb\@ne}
\@@end
"
" test: vim -S quicksort.vim
"
" quick sort
function! s:quicksort(target, left, right)
if a:left >= a:right | return [a:target[a:left]] | endif
let i = a:left | let j = a:right
let pivot = a:target[i]
while 1
while a:target[i] < pivot | let i += 1 | endwhile
while pivot < a:target[j] | let j -= 1 | endwhile
if i >= j | break | endif
let tmp = a:target[i] | let a:target[i] = a:target[j] | let a:target[j] = tmp
let i += 1 | let j -= 1
endwhile
let l_list = s:quicksort(a:target, a:left, i-1)
let r_list = s:quicksort(a:target, j+1, a:right)
return l_list + r_list
endfunction
" test
let list = [ 2, 6, 3, 8, 5, 4, 1, 9, 7 ]
echo "Result:"
echo s:quicksort(list, 0, len(list)-1)
@zakigatez

This comment has been minimized.

Copy link

zakigatez commented Dec 8, 2018

on 100000 value it does not work !!
i have the same problem with my algo

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.