Útfærið counting sort með hjálp fylkis sem telur tíðni gilda.
public class CountingSort
{
// Notkun: csort(f, max);
// Fyrir: Allar tölur í f eru á bilinu [0,max]
// Eftir: Búið er að raða f í vaxandi röð
public static void csort(int[] f, int max)
{
int[] count = new int[max + 1];
for (int i = 0; i < f.length; i++)
count[f[i]]++;
int k = 0;
for (int i = 0; i < count.length; i++)
{
for (int j = 0; j < count[i]; j++)
f[k++] = i;
}
}
public static void main(String[] args)
{
int[] f = {6,1,4,2,1,7,3,7,0,10,1};
int[] e = {0,1,1,1,2,3,4,6,7,7,10};
csort(f, 10);
for (int i = 0; i < f.length; i++)
{
System.out.println(f[i]);
if (f[i] != e[i])
{
System.out.printf("Test failed: expected %d got %d\n", e[i], f[i]);
return;
}
}
System.out.printf("Test passed.\n");
}
}
#include <stdio.h>
#define NELEMS(x) (sizeof(x) / sizeof(x[0]))
// Notkun: csort(f, n, max);
// Fyrir: Allar tölur í f[0..n-1] eru á bilinu [0,max]
// Eftir: Búið er að raða f[0..n-1] í vaxandi röð
void csort(int *f, int n, int max)
{
int count[max + 1];
int i, j;
for (i = 0; i <= max; i++)
count[i] = 0;
for (i = 0; i < n; i++)
count[f[i]]++;
int k = 0;
for (i = 0; i <= max; i++)
{
for (j = 0; j < count[i]; j++)
f[k++] = i;
}
}
int main(void)
{
int f[] = {6,1,4,2,1,7,3,7,0,10,1};
int e[] = {0,1,1,1,2,3,4,6,7,7,10};
int i;
csort(f, NELEMS(f), 10);
for (i = 0; i < NELEMS(f); i++)
{
printf("%d\n", f[i]);
if (f[i] != e[i])
{
printf("Test failed: expected %d got %d\n", e[i], f[i]);
return 1;
}
}
printf("Test passed.\n");
return 0;
}
Útfærið fall fyrir radix sort fyrir heiltölur með hjálp biðraða. Biðraðaútfærslu má finna hér fyrir neðan. Röðunarfallið skal taka eina biðröð sem viðfang og þegar snúið er til baka skal sú biðröð vera í vaxandi röð.
Útfærslan skal virka þannig að farnar eru nokkrar umferðir í lykkju, ein umferð fyrir hvern mögulegan tölustaf í inntaksgildunum frá hægri til vinstri. Þið megið gefa ykkur þá forsendu að gildin séu milli 0 og 999.
Í hverri umferð lykkjunnar gerið þið eftirfarandi:
Í lykkjunni þá er aðalbiðröðin (sú sem var tekin inn sem viðfang) tæmd yfir í 10 biðraðir eftir gildi tölustafsins sem er undir skoðun og síðan eru þær biðraðir tæmdar yfir í aðalbiðröðina aftur (og þá er búið að koma tölunum í röð skv. næsta tölustaf, enda eru biðraðirnar tæmdar í röð, þ.a. fyrst er q[0] tæmd, sem inniheldur 0-tölustaf í því sæti sem er undir skoðun, svo q[1], etc).
Forritið skal innihalda prófunarforrit í main sem raðar 10000 slembigildum og athugar hvort niðurstaðan er í réttri röð. Forritið skal síðan skrifa "Test passed" ef rétt er raðað, en annars "Test failed".
Þið megið leysa verkefnið í C eða Java. Skrifið notkunarlýsingu fyrir radix sort fallið ykkar og skrifið fastayrðingu fyrir sérhverja lykkju í radix sort fallinu.
import java.util.Random;
public class RadixSort
{
// Notkun: rsort(q);
// Fyrir: q inniheldur tölur á bilinu [0,999]
// Eftir: Búið er að raða q í vaxandi röð
@SuppressWarnings("unchecked")
public static void rsort(Queue<Integer> q)
{
Queue<Integer>[] r = new Queue[10];
for (int i = 0; i < 10; i++)
r[i] = new Queue<Integer>();
int k = 0;
int v = 1;
while (k < 3)
{
// q inniheldur sömu tölur og í upphafi kalls,
// í vaxandi röð þegar borið er saman á grundvelli
// k síðustu tölustafa í hverri tölu.
// 0 <= k <= 3, v=10^k
while (!q.isEmpty())
{
// q,r[0],...,r[9] innihalda samanlagt tölurnar
// sem voru í q í upphafi kalls. Í hverri biðröð
// eru tölurnar í vaxandi röð, þegar borið er saman
// á grundvelli k síðustu tölustafa. Allar tölurnar
// í q eru >= allar tölurnar í r[0],...,r[9] þegar
// borið er saman á grundvelli síðustu k tölustafa.
// r[0] inniheldur aðeins tölur þar sem síðasti
// (k+1)-sti tölustafur er 0, r[1] aðeins þar sem
// tölustafurinn er 1, o.s.frv.
int x = q.get();
int ri = (x/v) % 10;
r[ri].put(x);
}
for (int i = 0; i < 10; i++)
{
// q inniheldur minnstu tölur í vaxandi röð úr upphaflega
// q á grundvelli samanburðar síðustu (k+1)-stu tölustafa.
// Hinar tölurnar eru í r[i],...,r[9], 0 <= i <= 10
while (!r[i].isEmpty())
q.put(r[i].get());
}
v *= 10;
k++;
}
}
// Notkun: b = isSorted(q);
// Fyrir: Ekkert
// Eftir: b er satt þþaa. ef q var í vaxandi röð.
// Ef b er satt þá er q jafnframt tóm, en
// ef b er ósatt þá er innihald q óskilgreint.
public static boolean isSorted(Queue<Integer> q)
{
if (q.isEmpty())
return true;
int last = q.get();
while (!q.isEmpty())
{
int x = q.get();
if (x < last)
return false;
last = x;
}
return true;
}
public static void main(String[] args)
{
Random g = new Random();
Queue<Integer> q = new Queue<Integer>();
for (int i = 0; i < 10000; i++)
q.put(g.nextInt(1000));
rsort(q);
if (isSorted(q))
System.out.println("Test passed");
else
System.out.println("Test failed");
}
}
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "queue.h"
// Notkun: rsort(q);
// Fyrir: q inniheldur tölur á bilinu [0,999]
// Eftir: Búið er að raða q í vaxandi röð
void rsort(struct queue *q)
{
struct queue r[10];
int i;
for (i = 0; i < 10; i++)
queue_init(&r[i]);
int k = 0;
int v = 1;
while (k < 3)
{
// q inniheldur sömu tölur og í upphafi kalls,
// í vaxandi röð þegar borið er saman á grundvelli
// k síðustu tölustafa í hverri tölu.
// 0 <= k <= 3, v=10^k
while (!queue_empty(q))
{
// q,r[0],...,r[9] innihalda samanlagt tölurnar
// sem voru í q í upphafi kalls. Í hverri biðröð
// eru tölurnar í vaxandi röð, þegar borið er saman
// á grundvelli k síðustu tölustafa. Allar tölurnar
// í q eru >= allar tölurnar í r[0],...,r[9] þegar
// borið er saman á grundvelli síðustu k tölustafa.
// r[0] inniheldur aðeins tölur þar sem síðasti
// (k+1)-sti tölustafur er 0, r[1] aðeins þar sem
// tölustafurinn er 1, o.s.frv.
int x = queue_get(q);
int ri = (x/v) % 10;
queue_put(&r[ri], x);
}
for (int i = 0; i < 10; i++)
{
// q inniheldur minnstu tölur í vaxandi röð úr upphaflega
// q á grundvelli samanburðar síðustu (k+1)-stu tölustafa.
// Hinar tölurnar eru í r[i],...,r[9], 0 <= i <= 10
while (!queue_empty(&r[i]))
queue_put(q, queue_get(&r[i]));
}
v *= 10;
k++;
}
}
// Notkun: b = isSorted(q);
// Fyrir: Ekkert
// Eftir: b er satt þþaa. ef q var í vaxandi röð.
// Ef b er satt þá er q jafnframt tóm, en
// ef b er ósatt þá er innihald q óskilgreint.
int is_sorted(struct queue *q)
{
if (queue_empty(q))
return 1;
int last = queue_get(q);
while (!queue_empty(q))
{
int x = queue_get(q);
if (x < last)
return 0;
last = x;
}
return 1;
}
int main(void)
{
struct queue q;
int i;
srand(time(NULL));
queue_init(&q);
for (i = 0; i < 10000; i++)
queue_put(&q, rand() % 1000);
rsort(&q);
if (is_sorted(&q))
printf("Test passed\n");
else
printf("Test failed\n");
return 0;
}
Skrifið mergesort fyrir biðraðir í C eða Java. Þið fáið mergesort aðferðina sjálfa gefna, en þið eigið að útfæra aðferðirnar sem vantar í beinagrindina hér fyrir neðan (split og merge).
Sækið skrána ospd-random.txt sem inniheldur sömu gögn og ospd.txt skráin úr síðasta verkefni nema í handahófskenndri röð. Notið forritið til að raða gögnunum í henni (með shell redirection eins og er sýnt fyrir neðan) og athugið hvort úttakið sé í vaxandi röð.
hhg@hhg:~/t2/V7/d3$ java Mergesort < ospd-random.txt aa aah aahed aahing aahs aal aalii aaliis aals aardvark aardwolf [..] zymogram zymology zymosan zymosans zymoses zymosis zymotic zymurgy zyzzyva zyzzyvas hhg@hhg:~/t2/V7/d3$
import java.util.Scanner;
public class Mergesort
{
// Notkun: split(q,q1,q2);
// Fyrir: q1 og q2 eru tómar biðraðir, sem hver um sig
// hefur pláss fyrir helming gilda úr q (þ.e.
// fyrir (q.count()+1)/2 gildi).
// Eftir: Búið er að fjarlægja öll gildi úr q og setja
// helming þeirra í q1 og hinn helminginn í q2
// (það gæti munað einum í fjölda staka, ef
// fjöldinn er oddatala).
static public void split(Queue<String> q, Queue<String> q1, Queue<String> q2)
{
while (q.count() != 0)
{
// Búið er að fjarlægja sléttan fjölda talna úr q
// og bæta helming þeirra við q1 og hinum
// helmingnum við q2.
q1.put(q.get());
if (q.count() == 0) return;
q2.put(q.get());
}
}
// Notkun: merge(q1,q2,q);
// Fyrir: q er tóm biðröð, q1 og q2 eru biðraðir, sem
// innihalda gildi, sem eru í vaxandi röð frá
// fremsta til aftasta.
// q hefur pláss fyrir öll gildin í q1 og q2.
// Eftir: q1 og q2 eru tómar, gildin úr þeim eru í q í
// vaxandi röð frá fremsta til aftasta.
static public void merge(Queue<String> q1, Queue<String> q2, Queue<String> q)
{
while (!q1.isEmpty() && !q2.isEmpty())
{
// Búið er að fjarlægja núll eða fleiri minnstu
// tölur úr q1 og q2 og setja þær í q í vaxandi
// röð frá fremsta til aftasta.
if (q1.peek().compareTo(q2.peek()) <= 0)
q.put(q1.get());
else
q.put(q2.get());
}
while (!q1.isEmpty())
// Sama og að ofan, en auk þess er annað hvort q1
// eða q2 tóm.
q.put(q1.get());
while (!q2.isEmpty())
// Sama og að ofan, en auk þess er q1 tóm.
q.put(q2.get());
}
// Notkun: msort(q);
// Eftir: Búið er að raða gildunum í q í vaxandi röð
static public void msort(Queue<String> q)
{
if (q.count() < 2)
return;
Queue<String> q1 = new Queue<String>();
Queue<String> q2 = new Queue<String>();
split(q,q1,q2);
msort(q1);
msort(q2);
merge(q1,q2,q);
}
// Notkun: main(args);
// Fyrir: Aðalinntak inniheldur einungis strengi.
// Eftir: Búið er að lesa allar línur af aðalinntaki
// og skrifa þær í vaxandi röð á aðalúttak.
public static void main(String[] args)
{
Queue<String> q = new Queue<String>();
Scanner scan = new Scanner(System.in);
while (scan.hasNext())
{
q.put(scan.nextLine());
}
msort(q);
while (!q.isEmpty())
{
System.out.println(q.get());
}
}
}
#include <stdio.h>
#include <string.h>
#include "queue.h"
// Notkun: split(q,q1,q2);
// Fyrir: q1 og q2 eru tómar biðraðir, sem hver um sig
// hefur pláss fyrir helming gilda úr q (þ.e.
// fyrir (queue_count(q)+1)/2 gildi).
// Eftir: Búið er að fjarlægja öll gildi úr q og setja
// helming þeirra í q1 og hinn helminginn í q2
// (það gæti munað einum í fjölda staka, ef
// fjöldinn er oddatala).
static void split(struct queue *q, struct queue *q1, struct queue *q2)
{
while (!queue_empty(q))
{
// Búið er að fjarlægja sléttan fjölda talna úr q
// og bæta helming þeirra við q1 og hinum
// helmingnum við q2.
queue_put(q1, queue_get(q));
if (queue_empty(q)) return;
queue_put(q2, queue_get(q));
}
}
// Notkun: merge(q1,q2,q);
// Fyrir: q er tóm biðröð, q1 og q2 eru biðraðir, sem
// innihalda gildi, sem eru í vaxandi röð frá
// fremsta til aftasta.
// q hefur pláss fyrir öll gildin í q1 og q2.
// Eftir: q1 og q2 eru tómar, gildin úr þeim eru í q í
// vaxandi röð frá fremsta til aftasta.
void merge(struct queue *q1, struct queue *q2, struct queue *q)
{
while (!queue_empty(q1) && !queue_empty(q2))
{
// Búið er að fjarlægja núll eða fleiri minnstu
// tölur úr q1 og q2 og setja þær í q í vaxandi
// röð frá fremsta til aftasta.
if (strcmp(queue_peek(q1), queue_peek(q2)) <= 0)
queue_put(q, queue_get(q1));
else
queue_put(q, queue_get(q2));
}
while (!queue_empty(q1))
// Sama og að ofan, en auk þess er annað hvort q1
// eða q2 tóm.
queue_put(q, queue_get(q1));
while (!queue_empty(q2))
// Sama og að ofan, en auk þess er q1 tóm.
queue_put(q, queue_get(q2));
}
// Notkun: msort(q);
// Fyrir: Ekkert
// Eftir: Búið er að raða q í vaxandi röð
void msort(struct queue *q)
{
if (queue_count(q) < 2)
return;
struct queue q1;
struct queue q2;
queue_init(&q1);
queue_init(&q2);
split(q, &q1, &q2);
msort(&q1);
msort(&q2);
merge(&q1, &q2, q);
}
int main(void)
{
char line[4096];
struct queue q;
char *p;
queue_init(&q);
while (1)
{
if (fgets(line, sizeof(line), stdin) == NULL)
break;
if ((p = strchr(line, '\n')))
*p = 0;
queue_put(&q, strdup(line));
}
msort(&q);
while (!queue_empty(&q))
printf("%s\n", queue_get(&q));
return 0;
}
Gefið er svæði f[i..j-1] og tala s sem er sæti innan svæðisins. Skrifið fall í C eða Java sem skiptir fylkinu í tvö svæði þ.a.
f[i..k-1] <= f[k] <= f[k+1..j-1] f[k] er gildið sem var upphaflega í f[s]
Þá er búið að koma gildi í sæti k sem ætti heima þar ef fylkinu væri raðað. Þetta eina gildi er í sínu endanlega sæti, öll minni gildi (<=) eru í neðra svæðinu, f[i..k-1], í engri sérstakri röð, og öll stærri gildi (>=) eru í efra svæðinu, f[k+1..j-1], í engri sérstakri röð.
Notandi fallsins gefur upp svæði f[i..j-1] og sæti s með gildi til að skipta eftir. Fallið skilar að lokum nýju sæti k þar sem upphaflega f[s] gildið endaði eftir skiptinguna.
Fallið á að vera O(N) þar sem N er stærð svæðisins. Skrifið fastayrðingu fyrir sérhverja lykkju í partition fallinu.
import java.util.Random;
public class Partition
{
// Notkun: k = partition(f,i,j,k);
// Fyrir: f[i..j-1] er löglegt svæði í f,
// i <= k < j
// Eftir: Búið er að víxla gildum í svæðinu þ.a.
// f[i..k-1] <= f[k] <= f[k+1..j-1]
public static int partition(int[] f, int i, int j, int k)
{
int p = f[k];
int n = i+1;
swap(f, i, k);
for (int t = i+1; t != j; t++)
{
// [p| < p | >= p | ??? ]
// i n t j
if (f[t] < p)
{
swap(f, t, n);
n++;
}
}
// [p| < p | >= p ]
// i n j
n--;
swap(f, i, n);
// [ < p |p| >=p ]
// i n j
return n;
}
private static void swap(int[] f, int a, int b)
{
int tmp = f[a];
f[a] = f[b];
f[b] = tmp;
}
// Notkun: b = is_partitioned(f,i,j,k)
// Fyrir: f[i..j-1] er svæði í fylkinu f, i <= k < j
// f[i..j-1] má vera óraðað.
// Eftir: b er satt þþaa. að
// f[i..k-1] <= f[k] <= f[k+1..j-1].
static boolean is_partitioned(int[] f, int i, int j, int k)
{
for (int n = i; n != k; n++)
if (f[n] > f[k])
return false;
for (int n = k; n != j; n++)
if (f[n] < f[k])
return false;
return true;
}
public static void main(String[] args)
{
Random g = new Random();
for (int n = 0; n < 5; n++)
{
System.out.printf("Test %d:\n", n);
int[] f = {62,88,59,94,4,71,26,17,44,28,37,44,64,25,73,21,23,35,49,23};
int r = g.nextInt(f.length);
System.out.printf("[+] Partition by f[%d] = %d\n", r, f[r]);
System.out.printf("\t");
for (int i = 0; i < f.length; i++)
{
if (i == r)
System.out.printf("[%02d] ", f[i]);
else
System.out.printf("%02d ", f[i]);
}
System.out.println();
int k = partition(f, 0, f.length, r);
System.out.printf("[+] Partitioned. Pivot rests at f[%d] = %d\n", k, f[k]);
System.out.printf("\t");
for (int i = 0; i < f.length; i++)
{
if (i == k)
System.out.printf("[%02d] ", f[i]);
else
System.out.printf("%02d ", f[i]);
}
System.out.println();
System.out.printf("[+] Checking post condition: f[%d..%d] <= f[%d] <= f[%d..%d]\n", 0, k-1, k, k+1, f.length-1);
if (is_partitioned(f, 0, f.length, k))
System.out.printf("[+] PASSED\n");
else
System.out.printf("[-] FAILED\n");
System.out.println();
}
}
}
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NELEMS(x) (sizeof(x) / sizeof(x[0]))
static void swap(int *f, int a, int b)
{
int tmp = f[a];
f[a] = f[b];
f[b] = tmp;
}
// Notkun: k = partition(f,i,j,s);
// Fyrir: f[i..j-1] er löglegt svæði í f,
// i <= s < j
// f[s] er pivot gildi til að skipta eftir
// Eftir: Búið er að víxla gildum í svæðinu þ.a.
// f[i..k-1] <= f[k] <= f[k+1..j-1]
// Gildið í sæti k var upphaflega í sæti s.
int partition(int *f, int i, int j, int s)
{
int p = f[s];
int n = i+1;
int t;
swap(f, i, s);
for (t = i+1; t != j; t++)
{
// [p| < p | >= p | ??? ]
// i n t j
if (f[t] < p)
{
swap(f, t, n);
n++;
}
}
// [p| < p | >= p ]
// i n j
n--;
swap(f, i, n);
// [ < p |p| >=p ]
// i n j
return n;
}
// Notkun: b = is_partitioned(f,i,j,k)
// Fyrir: f[i..j-1] er svæði í fylkinu f, i <= k < j
// f[i..j-1] má vera óraðað.
// Eftir: b er satt þþaa. að
// f[i..k-1] <= f[k] <= f[k+1..j-1].
static int is_partitioned(int *f, int i, int j, int k)
{
int n;
for (n = i; n != k; n++)
if (f[n] > f[k])
return 0;
for (n = k; n != j; n++)
if (f[n] < f[k])
return 0;
return 1;
}
int main(void)
{
int i, n;
srand(time(NULL));
for (n = 0; n < 5; n++)
{
printf("Test %d:\n", n);
int f[] = {62,88,59,94,4,71,26,17,44,28,37,44,64,25,73,21,23,35,49,23};
int r = rand() % NELEMS(f);
printf("[+] Partition by f[%d] = %d\n", r, f[r]);
printf("\t");
for (i = 0; i < NELEMS(f); i++)
{
if (i == r)
printf("[%02d] ", f[i]);
else
printf("%02d ", f[i]);
}
printf("\n");
int k = partition(f, 0, NELEMS(f), r);
printf("[+] Partitioned. Pivot rests at f[%d] = %d\n", k, f[k]);
printf("\t");
for (i = 0; i < NELEMS(f); i++)
{
if (i == k)
printf("[%02d] ", f[i]);
else
printf("%02d ", f[i]);
}
printf("\n");
printf("[+] Checking post condition: f[%d..%d] <= f[%d] <= f[%d..%d]\n", 0, k-1, k, k+1, NELEMS(f)-1);
if (is_partitioned(f, 0, NELEMS(f), k))
printf("[+] PASSED\n");
else
printf("[-] FAILED\n");
printf("\n");
}
return 0;
}