Selection Sort Java และ Analysis

Question

ฉันได้เขียนรหัสการจัดเรียงการเลือกใน java ฉันรู้ว่าอัลกอริทึมพื้นฐาน แต่เนื่องจากฉันกำลังเรียนรู้ดังนั้นจึงต้องการข้อมูลของคุณเกี่ยวกับคุณภาพของโค้ด โปรดดูรหัส: package selection_sort;

import java.util.Scanner;

public class SelectionSort {

int [] arrayToBeSorted;
Scanner scan=new Scanner(System.in);


SelectionSort(){
    System.out.println("Enter the number of elements");
    int total=scan.nextInt();
    this.arrayToBeSorted=new int[total];
    for(int i=0;i<total;i++) {
        System.out.println("Enter the "+i+" number of elements");
        this.arrayToBeSorted[i]=scan.nextInt();
    }
    
}

public void Sort() {
    int minIndex,min;
    boolean swapRequired=false;
    for(int i=0;i<arrayToBeSorted.length;i++) {
        minIndex=i;
        min=this.arrayToBeSorted[i];
        for(int j=i+1;j<this.arrayToBeSorted.length;j++) {
            if(this.arrayToBeSorted[j]<min) {
                min=this.arrayToBeSorted[j];
                minIndex=j;
                swapRequired=true;
            }
        }
        if(swapRequired) {
            swap(i,minIndex);
        }
                    
    }
    
    for(int x:this.arrayToBeSorted) {
        System.out.print(x+" ");
    }
        
    }

public void swap(int i,int j) {
    
    //System.out.println("swap called, pos="+i+"and minindex="+j);
    int temp=this.arrayToBeSorted[i];
    this.arrayToBeSorted[i]=this.arrayToBeSorted[j];
    this.arrayToBeSorted[j]=temp;
    
    //System.out.println("------------");
    
}
public static void main(String[] args) {
    SelectionSort s=new SelectionSort();
    s.Sort();
}

}

นอกจากนี้เกี่ยวกับการวิเคราะห์เนื่องจากการเลือกคือ O (n2) เป็นเพราะฉันใช้ซ้อนสำหรับลูป มีเครื่องมือใดบ้างที่บอกเราเกี่ยวกับความซับซ้อนของโค้ดขอบคุณล่วงหน้าและโปรดอดทนรอหากมันไร้เดียงสามาก

Answer 1

int [] arrayToBeSorted;
Scanner scan=new Scanner(System.in);

ไม่มีตัวปรับแต่งใด ๆ สมาชิกและฟังก์ชันpackage-privateต่างๆ ซึ่งหมายความว่าสามารถเข้าถึงได้จากแพ็คเกจเดียวกัน แต่ไม่สามารถเข้าถึงได้จากอินสแตนซ์ที่ขยายคลาส นั่นเป็นสิ่งที่แปลกมากจริงๆแล้วเมื่อมองจากมุมมองเชิงวัตถุ คุณต้องการสร้างมันprivateขึ้นมาหรือถ้าชั้นเรียนขยายออกไปก็สามารถเข้าถึงprotectedได้

เช่นเดียวกันกับตัวสร้าง

---

    System.out.println("Enter the number of elements");
    int total=scan.nextInt();
    this.arrayToBeSorted=new int[total];

คุณสามารถใช้ a List/ ArrayListแทนอาร์เรย์ซึ่งหมายความว่าคุณสามารถรับตัวเลขจากผู้ใช้ได้มากเท่าที่พวกเขาต้องการโดยไม่ต้องระบุจำนวนก่อนล่วงหน้า สามารถใช้อินพุตว่างเพื่อประกาศจุดสิ้นสุดของรายการ อย่างไรก็ตามนั่นมีข้อเสียที่คุณต้องใช้Integerแทนintดังนั้นจึงยากที่จะบอกว่าอะไรดีกว่า นอกจากนี้ยังมีข้อเสียที่การตรวจสอบการป้อนข้อมูลที่ว่างเปล่าที่พร้อมใช้งานจากScannerที่คุณจะต้องใช้สำหรับการที่มีการแปลงด้วยตนเองเพื่อnextLineint

คุณยังสามารถเลียนแบบListโดยการเพิ่มอาร์เรย์แบบไดนามิก ไม่ว่าจะด้วยการทำสำหรับทุกรายการประสิทธิภาพก็ไม่สำคัญในกรณีการใช้งานนี้หรือเพิ่มขนาดเป็นสองเท่าเมื่อจำเป็น

---

this.arrayToBeSorted=new int[total];

คุณต้องการthisตัวปรับแต่งก็ต่อเมื่อคุณมีตัวแปรที่มีชื่อเดียวกันในขอบเขตเดียวกันตัวอย่างเช่นในตัวสร้าง:

public ValueContainer(int value) {
    this.value = value;
}

เป็นเรื่องปกติที่จะละเว้นthisหากไม่จำเป็น หากคุณเคยพบว่าตัวเองอยู่ในสถานการณ์ที่สับสนว่าจะใช้อินสแตนซ์ตัวแปรแบบคงที่หรือแบบโลคัลคุณได้ทำสิ่งผิดพลาดที่นั่นอยู่ดี

---

for(int i=0;i<total;i++) {

ฉันเป็นผู้สนับสนุนอย่างต่อเนื่องในการใช้ชื่อ "จริง" สำหรับตัวแปรในลูป

for (int counter = 0; counter < total; counter++) {
// or
for (int index = 0; index < total; index++) {

---

public void Sort() {

รูปแบบการตั้งชื่อ Java ระบุว่าเมธอด / ฟังก์ชันควรต่ำกว่าCamelCase

---

int minIndex,min;

โดยส่วนตัวแล้วฉันจะหลีกเลี่ยงการประกาศตัวแปรหลายตัวในบรรทัดเดียวกัน ทำให้พลาดการประกาศได้ง่าย

---

boolean swapRequired=false;

นี่เป็นตัวอย่างที่ดีของชื่อที่ดีสำหรับตัวแปรขอบคุณ!

---

    for(int x:this.arrayToBeSorted) {
        System.out.print(x+" ");
    }

น่าเสียดายที่เป็นชื่อที่ไม่ถูกต้องสำหรับตัวแปร ใช้เฉพาะ "x" "y" และ "z" เมื่อทำงานกับมิติข้อมูล "ค่า" หรือ "ตัวเลข" น่าจะเป็นชื่อที่ดีสำหรับที่นี่

---

โดยรวมก็ดูใช้ได้ ฉันไม่ได้เรียกใช้เพื่อทดสอบการทำงานแม้ว่า สิ่งที่คุณควรเปลี่ยนคือคุณมีตรรกะในตัวสร้าง ไม่มีใครคาดคิดว่าตัวสร้างจะเต็มไปด้วยตรรกะเพราะคุณมองไม่เห็นเจตนาของตรรกะจากพวกเขา พวกเขาควรจะไม่ทำอะไรให้มากที่สุด นั่นหมายความว่าคุณควรย้ายตรรกะลงหรือดียิ่งขึ้นลงsort mainตัวเรียงลำดับของคุณไม่ควรเกี่ยวข้องกับอินพุตเลยมันควรจะเกี่ยวข้องกับการเรียงลำดับค่าเท่านั้นตามหลักแล้วคลาสอื่น ( InputReader?) ควรเกี่ยวข้องกับการรับอินพุต สิ่งที่คุณทำได้มีดังนี้:

public static final void main(String[] args) {
    InputReader inputReader = new InputReader();
    
    int[] values = inputReader.readValues();
    
    Sorter sorter = new Sorter();
    sorter.sort(value);
    
    // TODO Print sorted output.
}

นอกจากนี้ยังมีส่วนกลับหัวที่คุณไม่จำเป็นต้องมีสถานะSorterเลยซึ่งจะทำให้เธรดปลอดภัยโดยค่าเริ่มต้น