تمرین مرتب سازی سریع

مرتب سازی سریع
مرتب سازی سریع

مرتب سازی سریع

یکی از الگوریتم های مرتب سازی یا Sort در زبان های برنامه نویسی و مباحث الگوریتمی، مرتب سازی به روش مرتب سازی سریع یا Quick Sort می باشد.

در این تمرین قصد بررسی این الگوریتم را داریم.

 

مرتب سازی سریع

یک آرایه از n عدد طبیعی داریم. می‌خواهیم اعضای آن را با استفاده از الگوریتم quicksort مرتب کنیم.

 

ورودی :

در خط اول ورودی ابتدا عدد n نشان‌گر تعداد اعداد آمده است. در n خط بعدی در هر کدام یک عدد می‌آید که نشان‌گر یکی از اعداد آرایه است.

 

خروجی :

در خروجی آرایه‌ی مرتب شده را در یک سطر چاپ کنید.

 

محدودیت‌ها :

n ≤ ۱۰۰۰۰۰

همه اعداد ورودی در int جا می‌شوند.

 

مثال :
ورودی نمونه :
۱۰
۱۰۰ ۱۴ ۱۰ ۵ ۲ ۷ ۴ ۹ ۵ ۸
خروجی نمونه :
۲ ۴ ۵ ۵ ۷ ۸ ۹ ۱۰ ۱۴ ۱۰۰

 

حل تمرین :
کلاس File :

یکی از کلاس های ثابت در تمارینی که ورودی آنها فایل متنی می باشد کلاس File می باشد؛

این کلاس وظیفه دریافت اطلاعات از ورودی و انتقال آنها به خروجی را دارد.

علت نامگذاری آن با نام کلاس File این موضوع است که داده های ورودی خروجی در این تمرین توسط فایل های متنی به برنامه منتقل خواهند شد.

import java.io.*;

public class File
{
    private String input_path;
    private String output_path;

    public File()
    {
        this.input_path = "d://input.txt";
        this.output_path = "d://output.txt";
    }
    public String[] read() throws IOException
    {
        FileInputStream input = null;
        String[] data=null;
        int i=0;
        try{
            input = new FileInputStream(input_path);
            DataInputStream dataInputStream = new DataInputStream(input);
            BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(dataInputStream));
            String strLine;
            while ((strLine=bufferedReader.readLine()) != null)
            {
                if(data==null)
                {
                    data = new String[1];
                    continue;
                }
                else if(i==1)
                {
                    break;
                }
                data[i] = strLine + (char) 13 + (char) 10;
                i += 1;
            }
        }
        finally
        {
            if(input == null)
            {
                input.close();
            }
        }
        return data;
    }
    public void write(String data, boolean append) throws IOException
    {
        BufferedWriter output = null;
        try
        {
            output = new BufferedWriter(new FileWriter(output_path, append));
            if(data==null)
                output.write("");
            else
                output.write(data + " ");
            output.close();
        }
        finally
        {
            if(output == null)
            {
                output.close();
            }
        }
    }
}

 

کلاس QuickSort :

در این کلاس برنامه ی ما داده های خود را گرفته حل خواهد کرد و نتایج را بر خواهد گرداند.

public class QuickSort
{
    private int counter;
    private int array_bound;
    private int[] array;
    private int partition(int arr[], int low, int high)
    {
        int left = low + 1;
        int right = high;
        int temp;
        int pivot = arr[low];

        while(left <= right)
        {
            while(arr[left] <= pivot && left <= right)
                left++;
            while(arr[right] > pivot && left <= right)
                right--;
            if(left < right)
            {
                if(left>=counter || right>=counter)
                    continue;
                temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        arr[low] = arr[right];
        arr[right] = pivot;
        return right;
    }

    QuickSort()
    {
        counter = 0;
        array_bound = 100000;
        array = new int[array_bound];
    }
    public void setArray(int value)
    {
        if(counter>100000)
            return;
        array[counter] = value;
        counter+=1;
    }
    public void sort(int low ,int high)
    {
        if (low < high)
        {
            int pivot = partition(array, low, high);
            sort(low, pivot - 1);
            sort(pivot + 1, high);
        }
    }
    public int[] result()
    {
        return array;
    }
    public int getCounter()
    {
        return counter;
    }
}

 

کلاس Main :

نقطه ی شروع برنامه این کلاس می باشد که حکم واسطه را بین کلاس File و QuickSort بازی می کند.

import java.io.*;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        File file = new File();
        file.write(null, false);
        QuickSort quicksort = new QuickSort();
        String[] construction = file.read();
        String job="";
        int[] result;

        for(String my_construction:construction)
        {
            for (int i=0; i<my_construction.length(); i++)
            {
                if(!Character.isWhitespace(my_construction.charAt(i)))
                {
                    job += String.valueOf(my_construction.charAt(i));
                }
                else
                {
                    if(!job.equals(""))
                        quicksort.setArray(Integer.valueOf(job));
                    job="";
                }
            }
        }
        quicksort.sort(0, quicksort.getCounter()-1);
        result = quicksort.result();
        int i=0;
        for (int my_result:result)
        {
            if(i>=quicksort.getCounter())
                break;
            System.out.println(my_result);
            file.write(String.valueOf(my_result),true);
            i+=1;
        }
    }
}

 

در صورت وجود هر سوالی از بخش نظرات امکان پرسش سوال خود را دارید.

منبع سوال سایت quera.ir می باشد ولی این مسئله به صورت اختصاصی توسط camelcase.ir حل شده است.

برای پیشنهاد حل مسئله توسط ما می توانید از بخش نظرات آدرس سوال یا متن سوال را فرستاده و در صورت امکان به آن سوال پاسخگویی خواهد شد.

در صورتی که علاقه به مشارکت دارید می توانید این مسئله را با زبان های دیگر برنامه نویسی حل کرده و برای ما ارسال کنید تا با نام شما برای دیگران به اشتراک بگذاریم.

برای امتیاز به این نوشته کلیک کنید!
[کل: 0 میانگین: 0]