File talk:Insertion sort animation.gif

{ read numbers to be sorted into the array }

       repeat
           Flag := true;
           for I := 1 to N - 1 do
               if (A[I] > A[I+1]) then
                   begin
                   Temp := A[I]; 
                   A[I] := A[I+1]; 
                   A[I+1] := Temp;
                   Flag := false;
                   end;
       until (Flag)

2. SAL code for bubble sort of integer array

.data n: .word 0 # input number a: .space 200 # 50 element array i: .word # array index J: .word # array index base: .word a # base address of array end: .word # address of last array element flag: .word 0 # completion flag prompt: .asciiz "Enter integers to be sorted, one per line. End with 0\n" result: .asciiz "Sorted list:\n" nl: .byte '\n'

.text __start: puts prompt # prompt for input la base, a # initialize base, end move end, base getin: get n # input numbers > 0 blez n, sort move M[end], n # store input in array add end, end, 4 # increment ending address b getin

sort: la i, a # bubble sort outer loop add J, i, 4 move flag, 0 # clear swap flag loop: ble M[i], M[J], noswap # if elements i & J out of order, swap move n, M[i] move M[i], M[J] move M[J], n move flag, 1 # set swap flag noswap: add i, i, 4 # increment i add J, J, 4 # increment J blt J, end, loop # test for end of array bgtz flag, sort # if a swap occurred, continue sort

put '\n' puts result la i, a print: put M[i] # print sorted array put '\n' add i, i, 4 blt i, end, print done

dec1 18% spim SPIM Version 4.4.2, Release: April 22, 1993 Copyright 1990-92 by James R. Larus (larus@cs.wisc.edu) Modified to read SAL code by Scott Kempf (scottk@cs.wisc.edu) See the file COPYING for license information (spim) load "bubble.s" (spim) run Enter integers to be sorted, one per line. End with 0 1 9 2 8 3 7 4 6 5 0

Sorted list: 1 2 3 4 5 6 7 8 9

(spim) exit dec1 19%

Insertions appear to be O(1) time

Each insertion seems to occur instantaneously. If we wanted to show insertion sort accurately, I think the items after the insertion point ought to be shuffled along one at a time. --Doradus (talk) 21:29, 10 January 2009 (UTC)