2

So i have this problem right here. I want to code non-preemptive priority scheduling algorithm and my way is to sort it since you wanna get the highest priority first as the algorithm says. If ever I have priority values inside an Array. example: job1 = 2 ; job2 = 5; job3 = 2; job4 = 4.

The algorithm is that when two or more jobs with equal priority are present, the processor is allocated to the one "who arrived first". From the examples above It should be expected to be sorted this way(descending order): job2 - job4 - job1 - job3.

Since job1 and job3 is having the same priority, I want job1 to be in first before job3.

Now my problem is this. What's the solution for the sort to get the job1 first and not the job3? Or is it already in the system that I might automatically sort this out. Because I never tried anything before if job3 goes first or last.

Roch
  • 69
  • 1
  • 8
  • you probably need a stable priority queue which is not common so it's not part of java collections, check this out http://stackoverflow.com/questions/21617098/making-a-java-priorityqueue-into-a-stable-priority-queue – K'' Jan 21 '16 at 21:06

3 Answers3

2

Priority Queue Data Structure already exists in Java , you can use that. Thread safe version is - PriorityBlockingQueue

You can define your custom comparator to keep queue sorted based on priority while maintaining insertion order when priorities equalize.

Lots of examples are here - Java: How do I use a PriorityQueue?

Other comparator strategies listed here

Refer this one too

Hope it helps !!

Community
  • 1
  • 1
Sabir Khan
  • 9,826
  • 7
  • 45
  • 98
1

You are talking about stable sorting, which keeps the order of equal value elements. Merge sort is stable, while quick sort is not. Collections.sort uses merge sort and should do the job in O(nlogn).

However, if time complexity is an issue and since the number of priorities is limited, radix sort should sort, generally (though not guaranteed), in O(sn), when n integer keys of size s are used.

Timotei
  • 78
  • 5
myin528
  • 522
  • 2
  • 7
  • how could i know if job1 comes first before job3 on a descending order?. Because i have the basis that if i have two or more equal priority, i should allocate the one that is inputted first, since job1 was inputted first before job3 regardless of equal priority. – Roch Jan 20 '16 at 07:35
  • I was assuming the jobs were stored to an array in the order of arrival. Comparator compares priorities of the jobs. – myin528 Jan 20 '16 at 07:39
  • i still didnt get it sorry – Roch Jan 20 '16 at 07:42
0

Stable sorting is the answer to your question, assuming that jobs are stored to the front of the back of the array when they arrive. So if Job 1 = 2 is inputted, then some other jobs, then Job 3 = 2, then the array will look something like this: [Job 1, Job x, Job y, ..., Job 3]. Stable sorting, by definition, means that if two elements in the array have the same value, then the original ordering of the two elements is preserved. As myin528 states, Mergesort is stable, as are radix sort, which could be faster depending on the values of your array, or insertion sort, if your array is small.

ghui
  • 156
  • 3
  • 12