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)
- 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
[edit]
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)
_time){kind=link}
