insertion sort


See On Github

Data

Contributor

Generic placeholder thumbnail

by kennyledet

in c

Source Code

CFLAGS="-Wall -g"

clean:
	rm -f insertion_sort

all: insertion_sort

insertion_sort:
	clang insertion_sort.c -o insertion_sort
ELF>@@P@8	@@@@@@88@8@@@ ((`(` PP`P`TT@T@DDPtd		@	@DDQtdRtd((`(`/lib64/ld-linux-x86-64.so.2GNUGNU؁rNX5\헳k( !__gmon_start__libc.so.6printfmemcpy__libc_start_mainGLIBC_2.14GLIBC_2.2.5:ui	E````HH5 % @% h% h% h1I^HHPTI@H@@Hp@HH) HtHÐUHSH=H uK@`HB H8`HHH9s$fDHH 8`H H9r
 H[]fff.H=	 UHtHt]H`]ÐUHHpH%@	@H4HME}HuHHH<%t	@E
uH}uEH}uH<%	@fH}uEgH<%	@HH}uE$u}H<%	@EH<%	@EHp]UHH H%	@H}uHǰEEE;E-H<%	@HcEHM4EEEH<%	@}EH ]@H|$t$D$D$;D$HcD$HL$T$T$T$|$D$HcD$HL$;T$@@t$D$5HcD$HL$t$HcHL$T$T$D$L$HcHt$D$D$4fH|$t$D$D$;D$DHcD$HL$t$HcHL$;
D$D$D$D$D$$ÐHl$Ld$H- L% Ll$Lt$L|$H\$H8L)AIHIHt1@LLDAHH9uH\$Hl$Ld$Ll$ Lt$(L|$0H8ÐUHSHH8 Ht(`DHHHuH[]ÐHH7%Sorting %d values in sequence Done sorting. Result Testing if result sort is valid....Yes!
No!
{%d, }
;@\\|\zRx$@FJw?;*3$"DAC
d|AC
0r$`Q_@X @
	@o@0@@
Q`H@@	o@oo@P`V@f@v@GCC: (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3.symtab.strtab.shstrtab.interp.note.ABI-tag.note.gnu.build-id.gnu.hash.dynsym.dynstr.gnu.version.gnu.version_r.rela.dyn.rela.plt.init.text.fini.rodata.eh_frame_hdr.eh_frame.ctors.dtors.jcr.dynamic.got.got.plt.data.bss.comment8@8#T@T 1t@t$Do@N@xV0@0Q^o@
ko@0z@@H @ @@@@@	@	0	@0		@	D(
@(
(`(8`8H`HP`P``0`(`(0(*R`.	0A8@T@t@@@0@@@	@
@ @@@
@	@0	@	@(
@(`8`H`P````(`
@(`*8`8H`E
@[(`j0`x
@@0`@H`
@$`P`$``
@% `0(`7	@=Q
`@|`@`m`  `0	@
@@8`
@
@r(`
p@ ,
@; @call_gmon_startcrtstuff.c__CTOR_LIST____DTOR_LIST____JCR_LIST____do_global_dtors_auxcompleted.6531dtor_idx.6533frame_dummy__CTOR_END____FRAME_END____JCR_END____do_global_ctors_auxinsertion_sort.c__init_array_end_DYNAMIC__init_array_start_GLOBAL_OFFSET_TABLE___libc_csu_finidata_start_edata_finiprintf@@GLIBC_2.2.5print_sequence__DTOR_END____libc_start_main@@GLIBC_2.2.5__data_start__gmon_start____dso_handlememcpy@@GLIBC_2.14_IO_stdin_used__libc_csu_init_end_starttest_insertion_sort__bss_startmain_Jv_RegisterClassesinsertion_sort_init
#include <stdio.h>
#include <stdbool.h>
// Kendrick Ledet 2013
/* Insertion Sort: Efficient algorithm for sorting a small # of elements

 * Definition:
 * Input: A sequence of n elements {A1, A2, ..., An}
 * Output: Permutation {A'1, A'2, ..., A'n} of Input such that A'1 <= A'2 <= ... <= A'n
 */

void print_sequence(int*, int);
void insertion_sort(int*, int);
bool test_insertion_sort(int*, int);

int main(int argc, char *argv[])
{
    int sequence[] = {3, 3242, 21, 55, 653, 19, 139, 459, 138, 45349, 19, 2, 1}; 
    int sequence_length = sizeof(sequence)/sizeof(sequence[0]);

    printf("Sorting %d values in sequence ", sequence_length);
    print_sequence(sequence, sequence_length);

    insertion_sort(sequence, sequence_length);

    printf("Done sorting. Result ");
    print_sequence(sequence, sequence_length);

    printf("Testing if result sort is valid....");
    int pass = test_insertion_sort(sequence, sequence_length);
    if (pass)
        printf("Yes!\n");
    else
        printf("No!\n");

    return 0;
}

void insertion_sort(int *sequence, int sequence_length)
{
    int marker, key_index, key;

    for (key_index = 1; key_index < sequence_length; key_index++) {  // traverse sequence, start at 2nd index
        key = sequence[key_index];
        marker = key_index - 1;  // set marker at first index left of current key index

        while (marker > -1 && sequence[marker] > key) {
            sequence[marker+1] = sequence[marker];  // if marker val greater than key, shift right
            marker = marker - 1;  // count left while current marker val is greater than key
        }
        sequence[marker+1] = key;  // replace key
    }
}

void print_sequence(int *sequence, int sequence_length)
{ 
    printf("{");
    for (int i = 0; i < sequence_length; i++)
        printf("%d, ", sequence[i]);
    printf("\b\b}\n");
}

bool test_insertion_sort(int *sequence, int sequence_length)
{
    for (int i = 1; i < sequence_length; i++) {
        if (sequence[i] < sequence[i-1])  // each value must be greater than the value before it.
            return false;
    }
    return true;
}