001 /*
002 * LAPIS utility classes
003 * Copyright (C) 1998-2002 Carnegie Mellon University. All rights reserved.
004 *
005 * This library is free software; you can redistribute it
006 * and/or modify it under the terms of the GNU Library
007 * General Public License as published by the Free Software
008 * Foundation, version 2.
009 *
010 * LAPIS homepage: http://www.cs.cmu.edu/~rcm/lapis/
011 */
012 package lapisx.sort;
013
014
015 public class PointerSort {
016 public static lapisx.util.Debug debug = lapisx.util.Debug.QUIET;
017 int[] a;
018 int[] b;
019
020 public PointerSort (int[] originalArray) {
021 a = originalArray;
022 b = new int[a.length];
023 for (int i = 0; i < b.length; i ++ )
024 b[i] = i;
025 debug.println("size: " + b.length);
026 // for (int i = 0; i < b.length; i ++ )
027 // b[i] = (int) (Math.random() *100);
028 }
029
030 private void swap(int i, int j) {
031 int temp = b[i];
032 b[i] = b[j];
033 b[j] = temp;
034 for (int k = 0; k < b.length ; k++ ) {
035 debug.print(" " +b[k] );
036
037 }
038 debug.println("");
039 debug.print("value " );
040 for (int k = 0; k < b.length ; k++ ) {
041 debug.print(" " +a[b[k]] );
042
043 }
044 debug.println("");
045
046 }
047 public int[] pointerArray() {
048 return b;
049 }
050 public void sort() {
051 sort (0,b.length-1);
052 }
053 public int get(int i) {
054 return b[i];
055 }
056 public void sort(int low, int high){
057
058 // Initialize pointers
059 int top = low,
060 bottom = high - 1,
061 part_index,
062 part_value;
063 debug.println("low: " + low + " high " + high);
064 // Do nothing if low >= high
065 if (low < high)
066 {
067 // Check if elements are sequential
068 if (high == (low + 1))
069 {
070 if (a[b[low]]> a[b[high]])
071 swap(high, low);
072 }
073 else
074 {
075 // Choose a partition element and swap it with the last value in
076 // the array
077 part_index = (int)((low + high) / 2);
078 part_value = a[b[part_index]];
079 swap(high, part_index);
080 debug.println("part index: " + part_index + " part value " + part_value);
081 do
082 {
083 // Inrement the top pointer
084 while ((a[b[top]] <= part_value) && (top <= bottom))
085 top++;
086 debug.println("top: " + top + " bottom: " + bottom);
087 // Decrement the bottom pointer
088 while ((top <= bottom) && (a[b[bottom]] > part_value)){
089 debug.println("top2: " + top + " bottom2: " + bottom);
090 bottom--;
091 debug.println("top3: " + top + " bottom3: " + bottom);
092 }
093 debug.println("bottom: " + bottom);
094 // Swap elements if pointers have not met
095 if (top < bottom)
096 swap(top, bottom);
097 } while (top < bottom);
098
099 // Put the partition element back where it belongs
100 swap(top, high);
101
102 // Recursive calls
103 sort(low, top - 1);
104 sort(top + 1, high);
105 }
106 }
107 }
108
109
110
111
112 }